10641064 SUSTech Online Judge
Problem 1064 --Find the smallest pre-order traversal(Iarge)

1064: Find the smallest pre-order traversal(Iarge)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 156  Solved: 39
[Submit][Status][Web Board]

Description

Give you a in-order traversal of a binary Tree. Please find the minimum pre-order traversal of the tree.

 

We compare pre-order by their alphabet order. For example:

If two pre-order are: {6, 4, 2, 3, 1, 5}, {6, 1, 2, 3, 5, 4},

Since 6 = 6, 4 > 1, the second one is smaller.

Input

First line is an integer T, which is the number of test cases. (1 <= T <= 10)

For each test case, there will be an integer in a single line N (1 <= N <= 50000). N is the number of nodes. The nodes are numbered from 1 to N.

Then there will be one line. Which is the in-order traversal of the Tree.

Output

Print the smallest pre-order traversal in a single line.

Sample Input

1
8
3 2 4 1 6 5 7 8

Sample Output

1 2 3 4 5 6 7 8

HINT

Bonus problem.

Source

[Submit][Status]