按照给定的扩展二叉树前序遍历序列建立相应的非空二叉树，要求采用二叉链表进行存储表示，并对其进行中序和后序遍历，输出中后序遍历序列后请销毁二叉链表以释放内存。

输入格式:

第一行为一个整数n，表示以下有n组数据，每组数据占一行，为扩展二叉树的前序遍历序列。

输出格式:

输出该二叉树的中序和后序遍历序列，每个序列占一行，每两组输出之间有一换行。

输入样例:

在这里给出一组输入。例如：

3
AB#D##C##
AB##C#D##
ABD##E##C#F##

结尾无空行

同学三连呀