Hacker

Bruno turns words into numbers with a rolling hash.

His algorithm works like this.

1. Start with hash $0$.
2. Read the characters of the string from left to right. For each one, multiply the current hash by $P$ and add the position of that character in the alphabet ($1$ to $26$).
3. The final hash is the remainder of that value divided by $M$.

Ivan got hold of a list of every string of length $N$ over the lowercase English letters, sorted lexicographically. The paper was torn, so only the part that begins with the string $S$ and ends with $\texttt{zz...z}$ is left.

Ivan wants to find $K$ distinct strings from the remaining list that have the same hash. Help him break Bruno's algorithm.

The first line contains the positive integers $P$ and $M$ from the statement. ($1 \le P, M \le 100000$)

The second line contains $N$, the length of the strings on the list. ($1 \le N \le 100000$)

The third line contains the string $S$, the first string of the remaining list. It has length $N$ and consists of lowercase English letters.

The fourth line contains $K$, the number of strings Ivan wants. ($1 \le K \le 20$)

The answer is fixed by this rule. Scan the remaining list in lexicographic order starting at $S$. Stop at the first string $t$ for which the strings from $S$ to $t$ include exactly $K$ strings whose hash equals the hash of $t$. Print those $K$ strings in lexicographic order, one per line. The last line is $t$.

If you reach the end of the list without any hash value collecting $K$ strings, print the single word $\texttt{NEMOGUCE}$.