Binary Search Tree

Interview

Time limit1sMemory limit256 MB

Summary

Given the preorder traversal of a binary search tree, print its postorder traversal.

Level: Medium6 of 10
Topics: Tree, Divide and conquer, Stack, Recursion
Solved: No attempts yet

Problem

A binary search tree is a binary tree that satisfies all three of the following conditions.

Every key in a node's left subtree is smaller than that node's key.
Every key in a node's right subtree is greater than that node's key.
The left and right subtrees are themselves binary search trees.

Binary search tree example

A preorder traversal (root → left → right) visits the root first, then the left subtree and the right subtree in order, printing each node's key. A postorder traversal (left → right → root) visits the left subtree and the right subtree first, and prints the root's key last.

Given the preorder traversal of a binary search tree, write a program that produces the postorder traversal of the same tree.

Input

The preorder traversal of the tree is given, one key per line. Each key is a positive integer smaller than $10^6$ , and there are at most 10,000 nodes. No two nodes share the same key.

Output

Print the postorder traversal of the given binary search tree, one key per line.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
4
2
1
3
6
5
7
```
Expected output
```
1
3
2
5
7
6
4
```