B - Puzzle of Lamps 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

AtCoder さんは、左から右へ一列に並べられた N 個の豆電球と、2 種類のスイッチ A, B で構成された装置を作りました。各豆電球は、0 (OFF) と 1 (ON) の 2 種類の状態をとります。各スイッチを押すと、以下のことが起こります。

  • スイッチ A を押すと、0 の状態の豆電球のうち一番左のものが 1 になる。
  • スイッチ B を押すと、1 の状態の豆電球のうち一番左のものが 0 になる。

なお、該当する豆電球が存在しない場合はスイッチを押せません。

最初、すべての豆電球は 0 の状態になっています。AtCoder さんは、左の豆電球から順に状態が S_1, S_2, \dots, S_N になっている状態にしたいです。そのためにスイッチをどの順番で何回押せばいいのかを答えてください。ここで、必ずしもスイッチを押す回数を最小化する必要はありませんが、操作を現実的な時間で終わらせるために、スイッチを押す回数は 10^6 回以下にしてください。なお、この問題の制約下では、答えが存在することが証明できます。

制約

  • 1 \leq N \leq 30
  • S_1, S_2, \dots, S_N は 0 または 1
  • S_1, S_2, \dots, S_N がすべて 0 であることはない
  • N は整数

入力

入力は以下の形式で標準入力から与えられます。 

N
S_1 S_2 \dots S_N

入力の 2 行目は長さ 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

出力の 2 行目は長さ m の文字列として出力してください。

入力例 1

5
01100

出力例 1

4
AAAB

この出力例で答えているのは、スイッチ A, A, A, B の順に押す操作方法です。以下の図のように、豆電球を目的の状態にすることができます。

別の方法として、スイッチ A, A, B, A, A, B の順に押しても、豆電球を目的の状態にすることができます。これに対応する以下の出力をした場合でも正解になります。

6
AABAAB

Score: 400 points

Problem Statement

Mr. AtCoder has created a device consisting of N small light bulbs arranged in a row from left to right, and two switches A and B. Each light bulb can be in one of two states: 0 (OFF) and 1 (ON). Pressing each switch causes the following:

  • Pressing switch A turns the leftmost light bulb in the 0 state into 1.
  • Pressing switch B turns the leftmost light bulb in the 1 state into 0.

If there is no applicable light bulb, you cannot press the switch.

Initially, all light bulbs are in the 0 state. He wants the states of the light bulbs to be S_1, S_2, \dots, S_N from left to right. Determine the order and number of times the switches should be pressed to achieve this. It is not necessary to minimize the number of presses, but it should be at most 10^6 so that the operations can finish in a realistic time. It can be proved that a solution exists under the constraints of this problem.

Constraints

  • 1 \leq N \leq 30
  • Each of S_1, S_2, \dots, S_N is 0 or 1.
  • Not all of S_1, S_2, \dots, S_N are 0.
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N
S_1 S_2 \dots S_N

Note that the second line is given as a string of length N.

Output

If your solution presses the switches m times (1 \leq m \leq 10^6) in the order t_1, t_2, \dots, t_m (each being A or B), print those in the following format:

m
t_1 t_2 \dots t_m

The second line should be printed as a string of length m.

Sample Input 1

5
01100

Sample Output 1

4
AAAB

This sample output presents a solution that presses the switches in the order A, A, A, B. This sets the light bulbs to the desired states, as shown in the figure below:

Alternatively, pressing switches in the order A, A, B, A, A, B also sets the light bulbs to the desired states. The following output corresponding to this solution would also be accepted:

6
AABAAB