Too Lazy To Move

Time Limit: 5 Seconds
Memory Limit: 32768 KB

As we all know, Hanoi Tower can be solved in 2^n-1 steps if there are n disks.
We might adhere to such rules:

1) When the step number is odd, move the smallest disk to the next pillar (in
the order A->B->C->A��).

2) When the step number is even, move one disk between the pillar without the
smallest disk.

Here is an example:

Step 0 (Initial Step)

A: 3 2 1

B:

C:

Step 1

A: 3 2

B: 1

C:

Step 2

A: 3

B: 1

C: 2

Step 3

A: 3

B:

C: 2 1

Step 4

A:

B: 3

C: 2 1

Step 5

A: 1

B: 3

C: 2

Step 6

A: 1

B: 3 2

C:

Step 7

A:

B: 3 2 1

C:

End.

Now it is your task to find out the m-th configuration for a n-disk Hanoi Tower
with the rules defined above.

**Input**

One test on each line, with two integers n (1 <= n <= 63) and m (0 <=
m <= 2^n-1). Input is terminated with end of file.

**Output**

Print a configuration in three lines. Conform to the format in the sample.
There should be one space after each colon. Each test is followed by a blank
line.

**Sample Input**

3 0

3 1

3 2

3 7

63 9223372036854775807

**Sample Output**

A: 3 2 1

B:

C:

A: 3 2

B: 1

C:

A: 3

B: 1

C: 2

A:

B: 3 2 1

C:

A:

B: 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39
38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1

C:

*
*

Author:

**CHENG, Long**
Source:

**ZOJ Monthly, March 2003**
Submit
Status