Reconstruct Preorder from Inorder and Postorder Traversals

Given the inorder and postorder traversals of a binary tree whose nodes are represented by distinct uppercase letters and the total number of nodes is at most \(8\), reconstruct and output the preorder traversal of the tree.

Note: A binary tree can be uniquely determined from its inorder and postorder traversals.

inputFormat

The input consists of two lines:

• The first line is a string representing the inorder traversal.
• The second line is a string representing the postorder traversal.

Both strings are non-empty, contain only uppercase letters, and have the same length.

outputFormat

Output a single line containing the preorder traversal of the binary tree.

sample

BAC
BCA

ABC