# 50136. Build Strings

## I'm a slow walker, but I never walk backwards.

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.

• 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.

## Sample Input 1

f 1 8 1


## Sample Output 1

fghijklm


## Sample Input 2

m 2 4 8


## Sample Output 2

mnopmnoqmnpqmnprmopqmoprmoqrmoqs


## Sample Input 3

t 3 3 5


## Sample Output 3

tuvtuwtuxtvwtvx


## Sample Input 4

w 4 3 7


## Sample Output 4

wabwacwadwaewxawxbwxy