Hash Code#7619
Sign in

Hash Code

1 second
128 megabytes
Hard

According to the Java standard library documentation, the hash code of a string is computed as

s[0] \times 31^{n - 1} + s[1] \times 31^{n - 2} + \ldots + s[n - 1]

where is the -th character of the string, is the length of the string, and ^ denotes exponentiation. Computation uses signed -bit integers in two's complement form.

Given an integer , your task is to construct distinct non-empty strings, each composed only of upper- and lowercase English letters, such that all of them have the same hash code according to the formula above. The length of each string must not exceed .

Input

The single line contains an integer (2 \le k \le 1000) — the number of distinct strings to generate.

Output

Output lines. Each line should contain a single string, non-empty and at most letters, composed only of upper- and lowercase English letters. All strings should be distinct and must have the same hash code.

Examples

Example 1

Loading
Loading