前序、中序转变为后序遍历

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

二叉树是一个使用且有趣的数据结构,在其应用中,常要求在在树种查找没肿特征的结点,或逐个进行处理,这就提出了遍历二叉树的问题,其中遍历又可以分为前序、中序和后序遍历,于是在学习过程中,我遇到了一个问题,我们能否根据所给出的前序和中序遍历,将其转换为后序遍历呢?烦请那位高手帮我解决这个问题。

Input

第一行输入一个整数t,表示cases ;对于每个case ,包括2行,分别输入前序,中序遍历(字符串长度在1到1000000之间)。

Output

输出后序遍历

Sample Input

2
FCADBEGHP
ACBDFEHGP
	
HDACBGFE
ADCBHFEG

Sample Output

ABDCHPGEF
ABCDEFGH

Hint

None

Source

JiHongkun

提交代码