题目描述

AtCoder 君制作了一个装置，由从左到右排列的一列 $N$ 个小灯泡和两种开关 A、B 组成。每个小灯泡有两种状态，0（关）和 1（开）。每当按下某个开关时，会发生以下情况：

• 按下开关 A 时，最左侧处于 0 状态的小灯泡会变为 1。
• 按下开关 B 时，最左侧处于 1 状态的小灯泡会变为 0。

如果不存在符合条件的小灯泡，则无法按下该开关。

最开始，所有小灯泡都处于 0 状态。AtCoder 君希望将小灯泡的状态依次变为 $S_1,\ S_2,\ \dots,\ S_N$。请你回答应该按照什么顺序、按多少次开关，才能实现目标状态。这里不要求按下开关的次数最少，但为了保证操作能在合理时间内完成，按下开关的总次数不得超过 $10^6$。在本题的约束下，可以证明一定存在解。

输入格式

输入通过标准输入给出，格式如下：

$N$
$S_1\ S_2\ \dots\ S_N$

注意，第二行以长度为 $N$ 的字符串形式给出。

输出格式

如果你的操作方案是按下 $m$ 次开关（$1 \leq m \leq 10^6$），依次按下的开关为 $t_1,\ t_2,\ \dots,\ t_m$（每个都是 A 或 B），请按如下格式输出：

$m$
$t_1\ t_2\ \dots\ t_m$

第二行应输出长度为 $m$ 的字符串。

样例 1

输入

5
01100

输出

4
AAAB

说明/提示

约束条件

• $1 \leq N \leq 30$
• $S_1,\ S_2,\ \dots,\ S_N$ 仅为 0 或 1
• $S_1,\ S_2,\ \dots,\ S_N$ 不全为 0
• $N$ 为整数

样例解释 1

该输出样例对应的操作顺序是依次按下开关 A、A、A、B。如下图所示，可以将小灯泡变为目标状态。

另外，也可以按下 A、A、B、A、A、B 的顺序，同样能达到目标状态。对应的输出如下，也是正确答案。

6
AABAAB

由 ChatGPT 4.1 翻译