The Unordered Towers Problem

You are given a variant of the classic Towers of Hanoi problem. Here, you have three pegs: A, B and C, and n distinct discs. Each disc has a unique radius equal to its label (i.e., the disc labeled i has radius i).

Initially, all discs are on peg A but they are not arranged in order (i.e. the order from top to bottom is arbitrary). Your goal is to move all the discs to peg C so that they appear in order – when reading from top to bottom, the discs are in strictly increasing order (that is, the top disc is the smallest and the bottom disc is the largest). Unlike the classical Towers of Hanoi problem, there is no restriction about placing a larger disc on a smaller one during the process.

You are allowed to perform no more than \(10^6\) moves. A move consists of taking the top disc from one peg and placing it on top of another peg.

Note: It is guaranteed that under the given constraints a solution sequence exists within the allowed move limit.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) \((1 \leq n \leq 1000)\), the number of discs.
2. The second line contains \(n\) space-separated integers. These represent the discs (by their labels) on peg A in order from top to bottom.

You may assume that these \(n\) numbers are a permutation of \(1, 2, \dots, n\).

outputFormat

First, output an integer \(k\) (the number of moves, \(k \leq 10^6\)). Then output \(k\) lines, each containing two uppercase letters separated by a space. Each line represents a move from one peg to another. The letters are one of A, B, or C. After performing all moves, pegs A and B must be empty, and peg C must contain all the discs in sorted order (from top to bottom, the sequence is in increasing order).

sample

1
1

2
A B
B C