Rebuilding binary search trees P36853

At the exercise is described a binary search tree with its preorder traversal, which includes a -1 for each leaf. But, in fact, it is not necessary to include the -1’s in the preorder of a search tree to be able to rebuild it.

Write a program that reads a sequence of binary search tree described with their preorder traversal with out -1’s. For each tree, it must write its postorder traversal.

Input

Input consists of a sequence of description of binary trees as it is explained at , with an exception: The -1 corresponding to the leaves are omitted. Suppose that trees are search trees and that its elements are natural numbers.

Output

For each tree of the input, your program must print a line with the postorder traversal of the tree. Each element must be preceded by a space.