Haymouth the cow never gets bored of eating bananas. (Did you know that cows eat bananas? Well, now you do.)
Except today. It's been such a long day that Haymouth has decided to watch other cows play the Tower of Hanoi.
The Tower of Hanoi begins with D discs of different sizes. Each disc has a hole so it can be slid onto any of the three vertical rods available. The D discs are all initially stacked in descending order of size on one of the rods (smallest at the top). The goal is to shift the whole stack to another rod, one disc at a time, such that at any point in time, discs on each of the three vertical rods remain in descending order of size. Also, a disc can only be moved from the top of one stack to the top of another stack.
Cows can actually be pretty good at this game. Haymouth observed that Moosa, his cow friend, always plays the game in the exact same way, completing it in 2^D - 1 moves. Getting hungry again, he numbered the discs from 1 to D in ascending order of size (where 1 represents the smallest disc) and put D bananas in a row on a platter. Following each game from the very beginning, Haymouth looks at the Bth column from the right when disc B is moved. If it is a banana, Haymouth eats it and places the banana peel there. If it is a banana peel, Haymouth replaces it with a fresh banana.
Moosa tells Haymouth that there is no need for the banana platter. He can immediately tell how the banana platter will look after N moves. Also, he can immediately tell how many moves were made so far just by looking at the banana platter. He tells Haymouth that watching a game of D discs should tell Haymouth how the platter will look in a game of D + 1 discs. The first 2^D states of the platter in the (D + 1)-disc game will be the 2^D states of the D-disc platters, prefixed by a banana. The following 2^D states of the (D + 1)-disc game will be the platters of the D-disc game in reverse order, prefixed by a banana peel.
Moosa is angry with Haymouth for eating all the bananas and is going to quiz Haymouth to prevent him from eating bananas.
Haymouth is too bloated to understand what Moosa meant and is going to eat bananas until you figure it out. Save the bananas!
Input and Output
The first line will be an integer M, the number of questions Moosa will ask Haymouth.
The next M lines will be of the form Q S, where Q is either 'a' or 'b' and S is a string of D 1s and 0s.
If Q is 'a', S represents the number of moves so far, N, in binary. You are to print D 1s and 0s, representing the state of the banana platter after N moves. Print 0 for a banana and 1 for a banana peel.
If Q is 'b', S represents the state of the banana platter. You are to print D 1s and 0s, representing the number of moves N in binary.
Subtask 1 (30%): 0 < M ≤ 10, 0 ≤ N ≤ 2^10 - 1.
Subtask 2 (68%): 0 < M ≤ 100, 0 ≤ N ≤ 2^20 - 1.
Subtask 3 (1%): 0 < M ≤ 100, 0 ≤ N ≤ 2^63 - 1.
Subtask 4 (1%): 0 < M ≤ 1000, 0 ≤ N ≤ 2^100 - 1.