eolymp
bolt
Try our new interface for solving problems
Problems

Hash Code Hacker

Hash Code Hacker

Time limit 1 second
Memory limit 128 MiB

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

s[0] * 31 ^ (n - 1) + s[1] * 31 ^ (n - 2) + ... + s[n - 1]

Here s[i] is the i-th character of the string, n is the length of the string, and ^ indicates exponentiation. Computation uses signed 32-bit integers in two's complement form.

Heather is going to hack the servers of Not Entirely Evil Recording Company (NEERC). To perform an attack she needs k distinct query strings that have equal hash codes. Unfortunately, NEERC servers accept query string containing lower- and uppercase English letters only.

Heather hired you to write a program that generates such query strings for her.

Input data

The single line contains integer k (2k1000) - the number of required query strings to generate.

Output data

Output k lines. Each line should contain a single query string. Each query string should be non-emptyand its length should not exceed 1000 characters. Query string should contain only lower- and uppercaseEnglish letters. All query strings should be distinct and should have equal hash codes.

Examples

Input example #1
4
Output example #1
edHs
mENAGeS
fEHs
edIT
Source 2015 ACM NEERC, Northern Subregion, October 24, Problem H