题目描述

我们把所有满足下列条件的字符串称为“单词”：

• 只包含大写字母 A 和 B；
• 长度至少为 2；
• 首字符必须是 A。

在每个单词上定义两种操作：

操作 R1

只改变最后一个字母：

• A 变成 B
• B 变成 A

其余字母保持不变。

操作 R2

设原单词为 w，构造新单词 t：

• t 的第一个字母一定是 A；
• 对于 i>1，t_i 由原单词中相邻的 w_{i-1} 和 w_i 决定：
  • 若 w_{i-1} = w_i，则 t_i = B
  • 否则 t_i = A

然后把 w 替换为 t。

若从某个单词 w 出发，按某种顺序连续执行 N 次 R1/R2 操作，满足：

1. 第 N 次操作后得到的结果再次等于原单词 w；
2. 中间出现的所有单词两两不同，且都不同于原单词 w；

则称这是 w 的一个 N-transformation。

给定 N > 1，请找出一个长度尽可能短的单词，使它存在 N-transformation；若不存在则输出 NO。

输入格式

输入一个正整数 N (N > 1)。

输出格式

若存在解，输出：

• 第 1 行：一个长度最短的合法单词；
• 第 2 行：一个长度为 N 的仅由 1 和 2 组成的字符串，表示依次执行的规则编号（1 表示 R1，2 表示 R2）。从第一行给出的单词开始按顺序执行这些操作后，应当第一次重新得到它自己，且中途不出现重复单词。

若不存在解，则输出一行 NO。

数据范围

• 2 <= N <= 100000
• 20% 数据：N <= 30
• 40% 数据：N <= 200
• 70% 数据：N <= 10000

样例

输入

6

输出

AABB
221212

样例解释

长度小于 4 的单词都不能作为某个 6-transformation 的起点；而长度为 4 的单词 AABB 可以，其对应变换序列如下：

AABB -> ABAB -> AAAA -> AAAB -> ABBA -> ABBB -> AABB

评分说明

• 若正确判断“无解”，该测试点得满分；
• 若输出的第一行不是合法单词，或第二行不是所要求的 N-transformation，则该测试点得 0 分；
• 否则，得分与第一行单词长度距离最优长度的接近程度有关。