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.

Public test cases

**Input**

10 180 155 60 80 170 300 240 400 310 340 3 30 20 10

**Output**

80 60 170 155 240 340 310 400 300 180 10 20 30

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions