Inorder Traversal Reconstruction from Preorder and Postorder

Given a binary tree's preorder and postorder traversals, reconstruct an inorder traversal. Note that a unique inorder sequence does not always exist, as different binary trees can yield the same preorder and postorder traversals. You may output any valid inorder traversal that corresponds to the given traversals.

The standard relationships in binary trees are: preorder: \(\text{root} \to \text{left subtree} \to \text{right subtree}\), inorder: \(\text{left subtree} \to \text{root} \to \text{right subtree}\), and postorder: \(\text{left subtree} \to \text{right subtree} \to \text{root}\).

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 10^5)\), representing the number of nodes in the tree.

The second line contains \(n\) space-separated integers representing the preorder traversal of the binary tree.

The third line contains \(n\) space-separated integers representing the postorder traversal of the binary tree.

outputFormat

Output a single line with \(n\) space-separated integers representing an inorder traversal of a binary tree whose preorder and postorder traversals are given. If there are multiple valid answers, output any one of them.

sample

1
1
1

1