Generating Colliding Query Strings

Heather is on a mission to hack the servers of the Not Entirely Evil Recording Company (NEERC). For her plan, she needs k distinct query strings that all share the same Java hash code. The Java hash code of a string s of length n is computed as follows:

$$\text{hash}(s) = s[0]\times 31^{n-1} + s[1]\times 31^{n-2} + \cdots + s[n-1] $$

Here, s[i] is the ASCII value of the i-th character and the arithmetic is done using signed 32-bit two's complement integers. Note that the allowed characters in the query strings are only the uppercase and lowercase letters of the English alphabet.

Your task is to generate k distinct strings made up solely of English letters such that every string has exactly the same hash code according to the Java specification. Any valid set of strings satisfying this condition will be accepted.

Hint: One known collision pair is "Aa" and "BB", since:

• hash("Aa") = 65×31 + 97 = 2112
• hash("BB") = 66×31 + 66 = 2112

You can use these blocks to construct longer strings. For example, by concatenating blocks, if every block has the same hash (i.e. 2112), then regardless of the order, the entire string will have the same overall hash code.

inputFormat

The input consists of a single integer k (1 ≤ k ≤ some reasonable limit), representing the number of distinct query strings you need to generate.

For example:

3

indicates that you must output 3 distinct strings that all have the same Java hash code.

outputFormat

Output k lines, each line containing a distinct query string composed only of uppercase and lowercase English letters. All these strings must have identical Java hash codes as defined above.

sample

1

Aa