Reconstruct Postorder Traversal from Inorder and Preorder

Farmer John cares a great deal about the pedigree of his cows. He has recorded their genealogy in a binary tree and documented the tree in a linear fashion using its inorder and preorder traversals rather than drawing the actual tree diagram.

Your task is to produce the postorder traversal from the given inorder and preorder traversals. Each cow's name is represented by a unique uppercase letter. You may assume that the tree has no more than \(26\) nodes.

The traversal orders are defined as follows:

• \(\textbf{Inorder:}\) left subtree, root, right subtree.
• \(\textbf{Preorder:}\) root, left subtree, right subtree.
• \(\textbf{Postorder:}\) left subtree, right subtree, root.

Example:

       C
      / \
     /   \
    B     G
   / \   /
  A   D H
     / \
    E   F
Inorder:  ABEDFCHG
Preorder: CABDEFGH
Postorder: AEFDBHGC

inputFormat

The input consists of two lines:

1. The first line contains a string representing the tree's inorder traversal.
2. The second line contains a string representing the tree's preorder traversal.

Each uppercase letter represents the unique name of a cow. The tree contains at most \(26\) nodes.

outputFormat

Output a single line containing the tree's postorder traversal.

sample

ABEDFCHG
CABDEFGH

AEFDBHGC