Problem Description

The Tower of Hanoi is a classic math problem.

Given three pegs A, B, and C, peg A has $n$ disks of different sizes stacked in order, with the largest at the bottom and the smallest at the top. Now you need to move all disks from peg A to peg C. What is the minimum number of moves required?

The minimum number of moves is $2^n - 1$. Moreover, if you must finish in the minimum number of moves, there is only one possible sequence of moves.

For example, when $n = 3$, you need a total of $7$ moves:

Move $1$: move the smallest disk from A to C, written as A->C;

Move $2$: move the 2nd smallest disk from A to B, written as A->B;

Move $3$: move the smallest disk from C to B, written as C->B;

Move $4$: move the 3rd smallest disk from A to C, written as A->C;

Move $5$: move the smallest disk from B to A, written as B->A;

Move $6$: move the 2nd smallest disk from B to C, written as B->C;

Move $7$: move the smallest disk from A to C, written as A->C.

Now, between move $x$ and move $y$, how many times does A->B occur, how many times does A->C occur, how many times does B->A occur, how many times does B->C occur, how many times does C->A occur, and how many times does C->B occur?

Input Format

The first line contains an integer $n$.

The second line contains two integers $x, y$, separated by a space.

Output Format

Output six lines, each containing one integer, representing the answers to the six questions above.

3
2 6

1
1
1
1
0
1

Hint

Constraints

For $30\%$ of the testdata, $1 \le n \le 10$, $1 \le x \le y \le 2^n - 1$.

For $60\%$ of the testdata, $1 \le n \le 30$, $1 \le x \le y \le 2^n - 1$.

For all testdata, $1 \le n \le 100$, $1 \le x \le y \le 2^n - 1$, and $y \le 10^{18}$.

Translated by ChatGPT 5