해시 코드 해커

자바 표준 라이브러리 문서에 따르면 문자열의 해시 코드는 다음과 같이 계산한다.

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

$s[i]$는 문자열의 $i$번째 문자이고 $n$은 문자열의 길이다. 계산은 2의 보수 방식의 부호 있는 32비트 정수로 하므로, 넘침이 일어나면 하위 32비트만 남는다.

헤더는 어느 회사의 서버를 공격하려고 한다. 공격하려면 해시 코드가 모두 같은 서로 다른 질의 문자열 $k$개가 필요하다. 그런데 서버는 영어 대문자와 소문자로만 이루어진 질의 문자열만 받는다.

헤더를 대신해 그런 질의 문자열을 만드는 프로그램을 작성하시오.

첫째 줄에 만들어야 하는 질의 문자열의 개수 $k$가 주어진다. ($2 \le k \le 1000$)

질의 문자열 $k$개를 한 줄에 하나씩 출력한다. 각 질의 문자열은 비어 있지 않고, 길이가 1000자를 넘지 않으며, 영어 대문자와 소문자로만 이루어진다. $k$개는 서로 달라야 하고 해시 코드는 모두 같아야 한다.

조건을 만족하는 답이 여러 가지이므로, 채점을 위해 답을 다음 하나로 정한다. $2^m \ge k$를 만족하는 가장 작은 음이 아닌 정수를 $m$이라고 하자. $i = 0, 1, \ldots, k-1$ 각각에 대해 $i$를 앞자리를 0으로 채운 $m$자리 이진수로 쓴 다음, 숫자 0은 Aa로, 숫자 1은 BB로 바꾼다. 이렇게 얻은 문자열을 $i$가 커지는 순서로 출력한다.

Aa와 BB는 두 문자짜리 조각의 해시 계산에서 값 $2112$로 같으므로, 이 규칙으로 만든 문자열 $k$개는 길이가 $2m$으로 모두 같고 해시 코드도 모두 같다. $k \le 1000$이라 $m \le 10$이고 길이는 20자를 넘지 않는다.