Binary Tree Traversal

Problem Background

Special for beginners, ^_^

Problem Description

Trees and binary trees generally have pre-order, in-order, post-order and level-order traversals. Given the in-order sequence and one other traversal sequence, the structure of the tree is uniquely determined.

Suppose each node of a binary tree is described by a single character. You are now given the in-order and level-order traversal strings; output the pre-order traversal string of the tree.

Input Format

Two lines in total, each a string of letters (all characters on a line are distinct), giving the in-order and level-order traversal sequences respectively. Each string's length is less than $50$.

Output Format

Exactly one line: the pre-order sequence of the binary tree.

Sample Input

DBEAC
ABCDE

Sample Output

ABDEC

Constraints

Length of each string $< 50$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• The first character of the level-order is the root. Find that root in the in-order string: everything to its left is the left subtree, everything to its right is the right subtree.
• Repeat recursively to recover the whole tree, then print pre-order.