Background

The Tower of Hanoi (also called the Hanoi Tower) problem is as follows: there are three pegs on a wooden board. On peg 1 there are three disks, with smaller disks on top and larger disks at the bottom (the initial state). The test subject needs to move the three disks on peg 1 to peg 3 (the target state). The rules are: each move can only take the top disk from any peg, and a larger disk cannot be placed on top of a smaller disk.

The solving process of a general problem solver is the strategy of means–ends analysis.

Problem Description

However, you may not have heard of the “Tower Outside Hanoi” problem. In fact, it seems that there is no such problem. So the great X_Xy decided to create one.

Since it is an extension of the Tower of Hanoi problem, it should share some similar parts: there are three pegs $A$, $B$, and $C$, and $n$ disks. The disk with label $i$ has radius $i$. All disks start on $A$, and in the end they must all be moved to $C$ in order (that is, from top to bottom, from small to large).

Since it is an extension of the Tower of Hanoi problem, it should also have some differences: the disks on $A$ at the beginning are not in order. Because of this restriction, we also do not care about the order during the moving process, which means you are allowed to place a larger disk on top of a smaller disk.

But X_Xy is very lazy. He only wants you to perform at most $10^6$ operations.

Input Format

The input has two lines.

The first line contains an integer $n$, the number of disks.

The second line contains $n$ integers, representing the labels of all disks on $A$ from top to bottom. It is guaranteed that the disks form a permutation of $1\sim n$.

Output Format

Output several lines.

The first line contains an integer $tot$, the number of operations.

The next lines, from line $2$ to line $tot$, each contain two uppercase letters separated by a space. Line $i+1$ indicates that your $i$-th operation moves a disk from one peg to another.

3
1 2 3

5
A B
A B
A C
B C
B C

Hint

For all testdata: $1\leqslant n \leqslant 4\times 10^4$.

Input Format

Output Format

Translated by ChatGPT 5