Stacks of Flapjacks

Write a program that, given as input a (description of a) stack of pancakes (sometimes referred to as flapjacks) of different sizes, outputs a description of how to sort the pancakes so that, going from the top of the stack to the bottom, the pancakes get larger in size.

The only operation that may be used in sorting the pancakes is the flip. A flip is carried out by inserting a spatula beneath one of the pancakes on the stack and then flipping (i.e., reversing the order of) all the pancakes above it. A flip is described by indicating the position of the pancake immediately above the spatula. Assuming that there are n pancakes on the stack, the positions on the stack are numbered from 0 to n-1, with 0 being the position of the pancake at the bottom. The sizes of the pancakes are given by the natural numbers 0 through n-1, as well. (In effect, the sizes are really ranks, with 0 denoting the smallest size and n-1 the largest.) You may assume that no two pancakes have the same size.

To illustrate the flip operation, consider the three stacks of pancakes below. (Each pancake is represented by its size.)

         2           4           3
         1           0           5
         0           1           2 
         4           2           1
         5           5           0 
         3           3           4
The stack on the left is transformed into the stack in the middle via flip(2). The middle stack is transformed into the stack on the right via flip(0).

The input consists of a sequence of stacks of pancakes. Each stack will have at least one pancake, but no more than 30. The input is terminated by end-of-file. Each stack is given by two lines of input, the first containing a natural number corresponding to the number of pancakes on the stack and the second containing the sizes of the pancakes on the stack, written top to bottom.

For each stack of pancakes, your program should produce three lines of output: the first line should echo the original stack, the second should give some sequence of flips that results in the stack becoming sorted, and the third should be blank.

Sample Input

5
0 1 2 3 4
5
4 3 2 1 0
4
1 2 0 3

Sample Output

0 1 2 3 4


4 3 2 1 0
0

1 2 0 3
2 1