Two-Color Hanoi Tower (hanoi)

Problem Background

Special for beginners, ^_^

Problem Description

Let $A, B, C$ be three peg stands. Initially, on peg $A$ there is a stack of $n$ disks, placed from bottom to top in decreasing order of size. The disks are numbered $1, 2, \dots, n$ from smallest to largest; odd-numbered disks are colored blue and even-numbered disks are colored red, as shown in the figure. The task is to move the stack of disks from peg $A$ to peg $B$, keeping the same order. When moving a disk, the following rules must be obeyed:

Rule (1): Only one disk may be moved at a time.

Rule (2): At no time may a larger disk be placed on top of a smaller disk.

Rule (3): At no time may two disks of the same color be placed on top of each other.

Rule (4): Subject to rules (1)-(3), a disk may be moved to any of the three pegs $A, B, C$.

Design an algorithm that moves the $n$ disks from peg $A$ to peg $B$ with the minimum number of moves, keeping the same order. For a given positive integer $n$, write a program to compute the optimal moving plan.

Input Format

The first line is the given positive integer $n$.

Output Format

Each line consists of a positive integer $k$ and two characters $c_1$ and $c_2$, meaning "move disk $k$ from peg $c_1$ to peg $c_2$".

Sample Input

3

Sample Output

1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B

Constraints

Time limit: 1s, memory limit: 1024KiB for each test case.