odd doctor 已更新

ZZX and Permutations

Time Limit
3s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(2/2)
Description:

ZZX likes permutations.

ZZX knows that a permutation can be decomposed into disjoint cycles(see https://en.wikipedia.org/wiki/Permutation#Cycle_notation). For example:
145632=(1)(35)(462)=(462)(1)(35)=(35)(1)(462)=(246)(1)(53)=(624)(1)(53)……
Note that there are many ways to rewrite it, but they are all equivalent.
A cycle with only one element is also written in the decomposition, like (1) in the example above.

Now, we remove all the parentheses in the decomposition. So the decomposition of 145632 can be 135462,462135,351462,246153,624153……

Now you are given the decomposition of a permutation after removing all the parentheses (itself is also a permutation). You should recover the original permutation. There are many ways to recover, so you should find the one with largest lexicographic order.

Input:

First line contains an integer t, the number of test cases.
Then t testcases follow. In each testcase:
First line contains an integer n, the size of the permutation.
Second line contains n space-separated integers, the decomposition after removing parentheses.

n105. There are 10 testcases satisfying n105, 200 testcases satisfying n1000.

Output:

Output n space-separated numbers in a line for each testcase.
Don't output space after the last number of a line.

Sample Input:
2
6
1 4 5 6 3 2
2
1 2
Sample Output:
4 6 2 5 1 3
2 1
Source:

2015 Multi-University Training Contest 4


Submit