JZPSTA - Stacks of Zippy

Recently Zippy received four stacks, named A B C D respectively. Firstly, there are n elements in stack A (the element sequence is a permutation of 1..n), and stack B C D are empty. He can do four types of operations:

  • operation a: push the top element of stack A to stack B (if stack A is not empty, this operation can be done.)
  • operation b: push the top element of stack B to stack D (if stack B is not empty, this operation can be done.)
  • operation c: push the top element of stack A to stack C (if stack A is not empty, this operation can be done.)
  • operation d: push the top element of stack C to stack D (if stack C is not empty, this operation can be done.)

He can do 2*n operations in total. Obviously, there are n elements in stack D after he did the 2*n operations. Then he take out the top element in stack D one by one. If the first element he takes out is n, the second is n-1, ... the last is 1, he will be very happy. Also, he wants to make the operation sequence he did lexicographic smallest.

Input

First line is a number t, which is the number of test cases. 

Then following t test cases. For each test case, the first line contains a number n, which denotes the number of the elements in stack A. The second line contains n numbers, separated by a space, which are the elements in stack A, from top to the bottom.

You can be sure that the sum of all n does not exceed 200000, and each n is not bigger than 100000.

Output

For each case, output a line. If there exists an answer, output the lexicographic smallest one (the operations Zippy does, separated by a space). If not, output 0.

Example

Input:
2
4
1 3 4 2
4
2 3 4 1
Output:
a b a c a b b d
0

Added by:sevenkplus
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:CNOIP2008 && POI17

hide comments
2012-08-22 13:03:36 :D
If I remember correctly, mine was O(N*log(N)) but it can be optimized to linear. I was planning to try it out, but I was too lazy :)
2012-07-22 21:30:39 Siarhei Kulik
Got AC with O(NlogN) after a lot of weird constant optimisation .. is there any linear solution?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.