Write a program to generate strings according to three constraints. First the first letter of this string must be a given letter $C$. Next the length of the string must be a given $L$. Finally, the distance between a letter and the letter after it must be no more than $K$. For example, if $C$ is 'a' and $K$ is 4, then the second letter of this string can only be one from the set {'b', 'c', 'd', 'e'}. Note that the distance between the letters is circular. That is if $C$ is 'w' and $K$ is 5, the second letter be one from {'x', 'y', 'z', 'a', 'b'} in a wrapped around manner. The same rule applied to every letter in the string, e.g., between the second and the third letter etc.
Write a program to generate strings recursively, and print the first $N$ strings in dictionary order. All letters are in lowercase.
Input Format
The input contains only one test case. There are one character $C$ and three integers $K$, $L$, and $N$ in one line. $C$ is the leading character of strings, $K$ is the maximum distance between consecutive letters, $L$ is the length of the strings, and $N$ is the number of strings you need to print.
$0 \lt K \lt 26$
$0 \lt L \lt 1024$
$0 \lt N \leq K^{L-1}$
Output Format
Output contains $N$ lines. There is a string in each line.
Subtasks
10 points: $K$ is 1, and there will be no wrapped around manner. $N$ is so large that you need to print all possible strings.
30 points: There will be no wrapped around manner. $N$ is so large that you need to print all possible strings.
30 points: There will be no wrapped around manner, but you need to print only the first $N$ strings.
30 points: There could be wrapped around manner, and you need to print only the first $N$ strings.