Reconstruct BST from Preorder Traversal and Print Inorder

You are given a string of space‐separated integers which represents the preorder traversal of a Binary Search Tree (BST). Your task is to reconstruct the BST from this traversal and then print its inorder traversal.

The BST has the property that for any node with value \(v\), all values in its left subtree are less than \(v\) and all values in its right subtree are greater than \(v\). The preorder traversal visits nodes in the order: root, left subtree, then right subtree. The inorder traversal of a BST always produces a sorted sequence in ascending order.

If the input is an empty string, the tree is considered empty and nothing should be printed.

Note: You are expected to read input from stdin and write the output to stdout.

inputFormat

The input consists of a single line containing space‐separated integers representing the preorder traversal of a BST. An empty input corresponds to an empty tree.

Format:

preorder

For example:

8 5 1 7 10 12

outputFormat

Print a single line output which is the inorder traversal of the reconstructed BST. The integers should be printed in ascending order, separated by a single space. If the tree is empty, print nothing.

Format:

inorder_traversal

For example, for the above input, the output should be:

1 5 7 8 10 12

## sample

8 5 1 7 10 12

1 5 7 8 10 12