URI Online Judge | 1606

The Hints of Ali Baba

By Marcio T. I. Oshiro Brazil

Timelimit: 1

One Thousand and One Nights is a collection of Arabic stories that date back to the ninth century. Some translations have been made to the West from the seventeenth century, and some of these stories, such as "Sinbad the Sailor", "Aladdin and the Magic Lamp" and "Ali Baba and the Forty Thieves" are now known to children around the world. In the story of Ali Baba the treasures are stored in a cave that opens when the words "Open Sesame" is used. In fact, the treasure was hidden in a safe in the cave wall, which opened when a permutation of the integers from 1 to N was recited. Not all 40 thieves had good memory, so Ali Baba had to maintain on the walls of the cave, hints on how to reconstruct the permutation, if any of the thieves forget. He wrote down a sequence of integers a1, a2, ... , ak generated from the permutation that opened the safe after possible applications of the following operations: duplication (i, j) and mirroring (i, j), for ij. The doubling operation (i, j) creates a copy of the subsequence ai, ai+1, ... , aj and inserted between aj and aj+1. The mirroring operation (i, j) inserts an inverted copy of the subsequence ai to aj (aj, aj-1, ..., ai) between aj and aj+1.

For exemple, given the sequence (a1, a2, a3, a4, a5, a6), the aplication of the mirroring operation (3,5) generates the sequence (a1, a2, a3, a4, a5, a'5, a'4, a'3, a6).

Your task is recontruct the original permutation.


The entry consists of several instances and ends with the end of file (EOF).

The first line of each instance contains the integer K (2 ≤ K ≤ 105) and N (1 ≤ NK) indicating, respectively, the size of the sequence written by Ali Baba and the largest integer of the original permutation. The next line contains the entire sequence K, separated by a space.


For each instance, print a single line with the permutation sequence that originated the input sequence, with a space separating consecutive integers. If there is more than one possible permutation, anyone of them will be accepted.

Sample Input Sample Output

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

1 2

1 2 3