10611061 SUSTech Online Judge
Problem 1061 --Find the preorder Traversal

1061: Find the preorder Traversal

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 340  Solved: 198
[Submit][Status][Web Board]

Description

Give you the in-order and post-order traversal of a binary tree T. Please find the preorder traversal of T.

Input

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

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

Then there will be two lines.

The 1st/2nd line will be the in/post order traversal of the Tree.

Output

For each test case, please print the pre-order traversal of the tree.

Sample Input

1
8
7 2 4 1 5 3 8 6
7 2 4 5 8 6 3 1

Sample Output

1 4 2 7 3 5 6 8

HINT

Median problem.

Source

[Submit][Status]