Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
76 - ZOJ 7th Anniversary Contest - D
7 Levels of Binary Search Tree

Time Limit: 1 Second      Memory Limit: 32768 KB

Given N numbers and the structure of a binary search tree. Please output the postorder traversal sequence of the tree.

For example, given numbers 1~7 and the tree structure in the figure 1, we can fill in the numbers as shown in the figure 2. Hence the postorder traversal sequence is {2, 4, 3, 1, 7, 6, 5}.

Note

It is garanteed that the level of a tree is never more than 7 (the root is at level 1).

Input

Each case starts with a line containing an integer N (N <= 127) followed by N non-negative integers which are supposed to be in the tree.
The next line gives the number of levels, L, of the binary search tree.
In the following L-1 lines, each line contains the numbers of nodes in the left- and right-subtrees of an upper-level node (the root level is omitted). If the upper-level node has no child, nothing will be shown in the next line.
The figure 1 is described by Sample Input. The 1st line of the tree contains 4 and 2, meaning that the root has 4 nodes in its left-subtree and 2 nodes in its right-subtree. The 2nd line contains 0, 3, 0, and 1, meaning that for the root of the left-subtree, there are 3 nodes in its right-subtree; for the root of the right-subtree, there are 1 node in its right-subtree. Since at level 3, there is only one subtree which contains more than 1 node, the 3rd line indicates that the root of this subtree has 1 left child and 1 right child.

Output

For each test case, output the required postorder traversal sequence in a line. The numbers must be seperated by one space, and there must be no extra space at the end of the sequence.

Sample Input

7 3 2 1 5 4 6 7
4
4 2
0 3 0 1
1 1

Sample Output

2 4 3 1 7 6 5

Author: CHEN, Yue
Source: ZOJ 7th Anniversary Contest
Submit    Status