题目描述

树和二叉树都有先序、中序、后序、按层遍历等遍历顺序。给定中序遍历和另一种遍历序列，可以确定一棵二叉树的结构。

假定二叉树中的每个结点用一个字符表示。现在给出一棵二叉树的中序遍历和按层遍历，请求出这棵二叉树的先序遍历。

输入格式

输入共两行。

第一行包含一个字符串，表示二叉树的中序遍历。

第二行包含一个字符串，表示二叉树的按层遍历。

每个字符串中的字符互不相同。

输出格式

输出一行一个字符串，表示二叉树的先序遍历。

DBEAC
ABCDE

ABDEC

数据范围与提示

• 输入字符串由英文字母组成
• 同一字符串中的字符互不相同
• 两个输入字符串长度相同，且包含相同字符集合