QUANTUM COMPUTERS LABORATORY, UNIVERSITY OF ATHENS

Quantum computers operate at the level of subatomic particles, where a quantum binary digit can be considered to represent both 1 and 0 simultaneously! However, during measurement or observation, the 'uncertainty' is removed. For this reason, a quantum computer can theoretically perform many operations simultaneously. Quantum computers use properties such as the magnetic rotation (spin) of atomic nuclei to represent quantum binary digits, or "qubits." Organic compounds are mainly used to encapsulate qubits in suitable receptacles. With the help of such compounds, we can create clusters of qubits ranging in size from a few to several dozen qubits.

In the Quantum Computers Laboratory of the University of Athens, experimental computers have three qubit receptacles (~A~, ~B~, ~C~). To transfer a set of qubit clusters from ~A~ to ~C~, it should be done as follows: First, the cluster with the largest size should be transferred, followed by the one with the smallest size. Only one transfer of a cluster can be made at a time, and only through the three receptacles.

Example with 2 qubits:

Problem: Develop a program in one of the IOI languages that guides scientists on which qubits to move to which receptacle. We always start from ~A~ to reach ~C~ through ~B~. Assume that the receptacle ~A~ is filled with qubits as normal and that the qubits must be properly arranged in ~C~. In each case, the minimum possible movements must be made.

INPUT DATA

The file qubits.in contains exactly one integer indicating the number ~N~ of qubit clusters it contains, where ~3 \le N \le 20~.

OUTPUT DATA

The file qubits.out has pairs of characters ~A~ ~B~, ~A~ ~C~, ~B~ ~C~, ~B~ ~A~, ~C~ ~A~, ~C~ ~B~ per line with a space between them, expressing the movements of qubits between the receptacles.

Example of Input - Output Files

STDIN (qubits.in)

3

STDOUT (qubits.out)

A C
A B
C B
A C
B A
B C
A C

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 15 sec.