### Problem

In 1883, Edouard Lucas invented, or perhaps reinvented, one of the most popular puzzles of all times – the Tower of Hanoi, as he called it – which is still used today in many computer science textbooks to demonstrate how to write a recursive algorithm or program. First of all, we will make a list of the rules of the puzzle:

• There are three pegs: A, B and C.
• There are n disks. The number n is constant while working the puzzle.
• All disks are different in size.
• The disks are initially stacked on peg A so that they increase in size from the top to the bottom.
• The goal of the puzzle is to transfer the entire tower from the A peg to one of the others pegs.
• One disk at a time can be moved from the top of a stack either to an empty peg or to a peg with a larger disk than itself on the top of its stack.

A good way to get a feeling for the puzzle is to write a program which will show a copy of the puzzle on the screen and let you simulate moving the disks around. The next step could be to write a program for solving the puzzle in a efficient way. You don’t have to do neither, but only know the actual situation after a given number of moves by using a determinate algorithm.

It is well known and rather easy to prove that the minimum number of moves needed to complete the puzzle with n disks is . A simple algorithm which allows us to reach this optimum is as follows: for odd moves, take the smallest disk (number 1) from the peg where it lies to the next one in the circular sequence ; for even moves, make the only possible move not involving disk 1.

### Mean

n最大为100，m最大为(2^n)-1.

### Analysis

1. 把上面n-1个盘子移动到临时柱子，2^(n-1)
2. 把最下面的第n个盘子移动到目标位置，2^(n-1)+1步即1<<n步
3. 把n-1个盘子从临时柱子移动到目标柱子。2^n步

### Code

```import java.math.BigInteger;
import java.util.Scanner;

public class Main {

int[] cnt = new int;
BigInteger m;

void solve(int i, int from, int to) {
if(i < 0) return;
int tmp = 6 - from - to;
if(m.testBit(i)) {
cnt[from] -= i; cnt[tmp] += i;
--cnt[from]; ++cnt[to];
solve(i-1, tmp, to);
} else {
solve(i-1, from, tmp);
}
}

void run() {
Scanner cin = new Scanner(System.in);
while(true) {
int n = cin.nextInt();
m = cin.nextBigInteger();
if(n == 0 && m.equals(BigInteger.ZERO))
return;
cnt = n; cnt = cnt = 0;
if(n % 2 == 0) solve(n-1, 1, 3);
else solve(n-1, 1, 2);
System.out.println(cnt + " " + cnt + " " + cnt);
}
}

public static void main(String[] args) {
new Main().run();
}
}
```