시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB111100.000%

문제

You're going to launch a new online game that everybody will want to play. However, your servers are not ready to handle so many players. More precisely, your servers can handle $n$ players. Of course, you want as many players as possible, as that gives you as much income as possible. In other words, your goal is to have exactly $n$ players.

Acknowledging the state of your servers publicly would mean bad PR for your company. So you've decided the limit the number of players in a different way: by limiting their choice for usernames in such a way that there are exactly $n$ valid usernames.

The allowed usernames are strings that:

  • Have length exactly $k$.
  • Consist only of letters A and B.
  • Do not contain any string from the forbidden substring list $s_1, s_2, \dots, s_m$ as a substring.

You need to choose $k$, $m$, and the strings $s_1, s_2, \dots, s_m$ in such a way that there exist exactly $n$ valid usernames. See the output format for the restrictions on the values you choose.

입력

The only line of the input file contains one integer $n$, $1 \le n \le 10^9$.

출력

On the first line of the output file, print two integers $k$ and $m$: the length of the usernames, and the number of forbidden substrings. On the next $m$ lines print the forbidden substrings.

  • $1 \le k \le 60$.
  • $0 \le m \le 100$.
  • Each forbidden substring $s_i$ has length between 1 and $k$, and consists only of letters A and B.
  • There exist exactly $n$ valid usernames for the values you output.

It is guaranteed that a solution will always exist. You may output any valid solution. Forbidden substrings may coincide or be substrings of one another.

예제 입력 1

5

예제 출력 1

3 1
BB

예제 입력 2

6

예제 출력 2

3 2
ABB
BBB

예제 입력 3

8

예제 출력 3

3 0