Reconstruct Binary Tree

You are given two sequences representing the preorder and inorder traversals of a binary tree. Your task is to reconstruct the binary tree from these sequences. After constructing the tree, perform a preorder traversal and an inorder traversal of the tree, and print both traversals.

Recall that the preorder traversal of a binary tree visits the root node first, then the left subtree, and finally the right subtree, while the inorder traversal visits the left subtree, then the root node, and finally the right subtree. Given that the preorder and inorder arrays correspond to the same binary tree, your solution should correctly rebuild the tree.

The mathematical relation can be described as follows: if \(P = [p_0, p_1, \ldots, p_{n-1}]\) is the preorder and \(I = [i_0, i_1, \ldots, i_{n-1}]\) is the inorder traversal, then the first element \(p_0\) of the preorder list is the root. If the index of \(p_0\) in \(I\) is \(k\), then the left subtree’s inorder traversal is \(I[0, k-1]\) and the right subtree’s inorder traversal is \(I[k+1, n-1]\). The corresponding elements in the preorder list are used to construct the left and right subtrees recursively.

inputFormat

The input is given from standard input (stdin) in the following format:

n
preorder[0] preorder[1] ... preorder[n-1]
inorder[0] inorder[1] ... inorder[n-1]

Where:

• n is an integer denoting the number of nodes in the binary tree.
• The second line contains n space-separated integers representing the preorder traversal of the tree.
• The third line contains n space-separated integers representing the inorder traversal of the tree.

outputFormat

The output should be printed to standard output (stdout) as two lines:

preorder_traversal
inorder_traversal

Each output line is a space-separated list of integers, representing the preorder and inorder traversals of the reconstructed binary tree, respectively. These traversals should match the input order if the tree is built correctly.

## sample

7
3 9 20 15 7 8 12
9 3 15 20 8 12 7

3 9 20 15 7 8 12
9 3 15 20 8 12 7

</p>