
ZOJ Problem Set  2603
Consider the railroad station that has n deadends designed in a way shown on the picture. Deadends are numbered from right to left, starting from 1. Let 2^{n} railroad cars get from the right. Each car is marked with some integer number ranging from 1 to 2^{n}, different cars are marked with different numbers. You can move the cars through the deadends using the following two operations. If the car x is the first car on the path to the right of the deadend i, you may move this car to this deadend. If the car y is the topmost car in the deadend j you can move it to the path on the left of the deadend. Note, that cars cannot be moved to the deadend from the path to its left and cannot be moved to the path on the right of the deadend they are in. Your task is to rearrange the cars so that the numbers on the cars listed from left to right were in the ascending order and all the cars are to the left of all the deadends. One can prove that the required rearranging is always possible. Input The input contains multiple test cases. Each test case occupies two lines. The first line of each case contains n  the number of deadends (1 <= n <= 13). The second line contains 2^{n} integer numbers  the numbers on the cars, listed from left to right. A case with n = 0 ends up the input file.
Output For each case, output the sequence of operations in one line. Each operation is identified with the number of the car moved in this operation. The type of the operation and the deadend used are clearly determined uniquely. Sample Input 2 3 2 1 4 2 1 2 3 4 0 Sample Output 3 3 2 2 1 1 4 4 3 2 1 1 2 3 4 4 1 2 2 1 2 1 3 3 4 4 1 2 3 3 4 4 Author: Andrew Stankevich Source: Andrew Stankevich's Contest #6 