HAN01  Hanoi!
Little Sabrina loves solving puzzles. Last week she got a new puzzle: The "Tower of Hanoi" puzzle. This puzzle is based on an old legend: "The temple priests of Hanoi have to transfer a tower consisting of 64 fragile disks of gold from one part of the temple to another, one disk at a time. The disks are arranged in order, no two of them the same size, with the largest on the bottom and the smallest on top. Because of their fragility, a larger disk may never be placed on a smaller one, and there is only one intermediate location where disks can be temporarily placed. It is said that before the priests complete their task the temple will crumble into dust and the world will vanish in a clap of thunder." Sabrina reconstructed the problem with some coins of different size. She solved the puzzle for three coins in 7 steps, for four coins in 15 steps,... after solving the problem with 7 coins she had the hang of it. Yesterday she started to solve the puzzle with 31 coins and her optimal strategy. After hours of moving coins from one pile to the other she was very tired and went to bed. This was a bad idea! Her little brother Robin discovered the towers of coins and  whoops!  threw it on the floor. Then he noticed a sheet of paper: "Don't touch this towers! Steps: 16543". "Oh no!" Robin has to reconstruct the tower because his sister can get very, very angry... Your task is to help Robin to reconstruct the towers. Sabrina started the game with all disks on peg number one and her goal was to move the disks to peg number two. She used her optimal strategy and noted the number of steps she had done.
Input
The first line of input contains one integer t: The number of testcases. t lines follow. Each line contains two integers n (2< n< 61) and k (0< k< 2^{n}). n is the number of disks of the Hanoi puzzle and k the number of steps Sabrina had done. Please be careful, the number k can be very large, it may not fit in a 32 bit integer.
Output
Output the reconstructed configuration of the towers after k steps. For each testcase output three lines. One for each tower. Each line consists of the tower identifier (1,2,3) a colon, one space and the disk numbers (n,n1,...,2,1) which are separated by a ''character.
Example
Input: 3 3 6 32 889397450 31 16543 Output: 1: 1 2: 32 3: 1: 323128251817143 2: 302926131211109652 3: 2724232221201916158741 1: 3130292827262524232221201918171676 2: 15854321 3: 14131211109
hide comments
Patrick Schneider:
20141027 13:55:08
Why exactly is Erlang forbidden? 

setu basak:
20140611 17:55:09
any special case?? the answer correct for this sample test cases but i am getting wa :(


Garg Ankit:
20121031 16:38:59
sol id: 5525726

Added by:  Simon 
Date:  20050503 
Time limit:  2s 
Source limit:  8082B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL GOSU JSRHINO PERL6 
Resource:  Ulm Algorithm Course SoSe 2005 