Description

Trees and binary trees generally have traversal orders such as pre-order, in-order, post-order, and level-order. Given an in-order sequence and another traversal sequence, the structure of a binary tree can be determined.

Assume each node of a binary tree is represented by a character. Now, given the in-order and level-order traversal strings, determine the pre-order traversal string of the tree.

Input Format

Two lines, each containing a string composed of letters (each character in a line is unique), representing the in-order traversal and level-order traversal sequences of the binary tree, respectively.

Output Format

A single line representing the pre-order sequence of the binary tree.

DBEAC
ABCDE

ABDEC