题目描述

给定一棵二叉树的中序遍历和后序遍历的结果，请你还原出它的前序遍历。约定树中的每个结点用一个不同的大写字母表示，且二叉树的结点个数不超过 $8$。

输入格式

共两行，每行一个由大写字母组成的字符串，分别表示二叉树的中序遍历和后序遍历。

输出格式

共一行一个字符串，表示还原出的二叉树的前序遍历。

样例

BADC
BDCA

ABCD