Description

Given the inorder and postorder traversals of a binary tree, find its preorder traversal. (Assume that tree nodes are represented by distinct uppercase letters, and the number of nodes in the binary tree is $\le 8$).

Input Format

Two lines, each a string of uppercase letters, representing the inorder and postorder traversals of a binary tree.

Output Format

One line containing a string representing the preorder traversal of the binary tree.

BADC
BDCA

ABCD

Hint

[Problem Source]

NOIP 2001 Junior Problem 3.

Translated by ChatGPT 5