Obfuscated Trees

Interview

Time limit2sMemory limit512 MB

Summary

Decode a tree from its obfuscated token stream, where each internal node carries an ordering code and subtree count, then print its values in pre-order.

Level: Medium4 of 10
Topics: Tree, Recursion, Implementation
Solved: No attempts yet

Problem

A data service has to move trees of numbers between its offices without anyone reading them. The transmission is encrypted, but the service decided that encryption alone is not enough, so it obfuscates each tree first.

A tree is written out as text. The obfuscation picks one of three orderings at random for every node, and that choice decides how the node lays out its subtrees. The three orderings mean this:

pre-order: write the value of the node, then the subtrees from left to right.
in-order: write the first subtree, then the value of the node, then the second subtree.
post-order: write the subtrees from left to right, then the value of the node.

Whatever ordering a node uses, its subtrees always come out left to right.

Take the tree in the picture below. The root has value 5 and three subtrees. The first subtree is rooted at a node with value 7 that has one child, and that child has value 1 with leaves 2 and 8 below it. The second subtree is rooted at a node with value 3 with leaves 8 and 9 below it. The third subtree is the single leaf 2.

Apply pre-order at the root, post-order at the node valued 7 and at the node valued 1, and in-order at the node valued 3. The node values then come out in this order:

5 2 8 1 7 8 3 9 2

The tree cannot be rebuilt from that form alone, so extra information is added. The output of every node that is not a leaf is preceded by one or two numbers. First comes a negative number naming the ordering:

-1 for pre-order
-2 for in-order
-3 for post-order

For pre-order and post-order, a positive number follows the negative one and gives the number of subtrees of that node. An in-order node always has exactly two subtrees, so no count is written for it.

Written under this rule, the tree above becomes:

-1 3 5 -3 1 -3 2 2 8 1 7 -2 8 3 9 2

Read obfuscated trees and print the values of each tree in pre-order.

Input

The input holds a sequence of problems, one problem per line. Each line holds space separated integers. The first integer is the number of code values in that problem, $C$ ( $0 < C \le 2000$ ), followed by $C$ integers $V_i$ ( $-3 \le V_i \le 9$ ) that carry the obfuscated tree data.

The numbers stored in the tree are always in the range 0 to 9. Negative values appear only as ordering codes. A subtree count sits in the same range, so a node has at most 9 subtrees.

The end of the input is a line holding a single 0.

Output

For each problem, print one line with the values of its tree in pre-order, separated by single spaces.

Examples4

Example 1

Input

16 -1 3 5 -3 1 -3 2 2 8 1 7 -2 8 3 9 2
0

Expected output

5 7 1 2 8 3 8 9 2

Example 2
Input
```
1 5
0
```
Expected output
```
5
```
Example 3
Input
```
1 0
1 9
1 0
0
```
Expected output
```
0
9
0
```

Example 4

Input

4 -1 1 4 7
4 -2 1 2 3
6 -3 3 1 2 3 4
0

Expected output

4 7
2 1 3
4 1 2 3