Stephen最近学习了二叉树的有关内容，他创造了一种树“字符二叉树”。

字符二叉树是这样的：

1） 该二叉树是完全二叉树。

2） 每个节点下面有0~2个孩子。

为了简单化，我们按照层序方式插入。比如说：HEADSHOT，H作为根节点，EA作为H的两个孩子结点。而DS作为E的孩子，HO作为A的孩子。T是D的左孩子。

Stephen想向TX们炫耀，无奈他只会插入操作（笨……），TX们要支持编码，解码，还要支持三种方式的遍历……

Stephen请你编程解决问题。

【来源】

SPOJ HS08 HS08TTC（Tree traversal cipher）

https://hs.spoj.pl/problems/HS08TTC/

第一行是一个数字t（t<=10）代表测试数据个数。

接下来t行，每行描述了一组测试数据。每组数据如下格式：

数据的第一行为一个数n（n<=10000），和两个字符串，分别代表所操作字符串长度和两个命令。（第一个命令为：“INORDER”、“PREORDER”或“POSTORDER”，第二个为“ENCODE”或“DECODE”）

第二行为一个长度为n的字符串S，即所操作字符串。（由‘A’到‘Z’组成）

输出t行，每行一个字符串。

当第二个命令为“ENCODE”时，即“编码”：将S作为HS08TTC的层序遍历，输出其中序遍历（“INORDER”），前序遍历（“PREORDER”）或后序遍历（“POSTORDER”）。

当第二个命令为“DECODE”时，即“解码”：S作为中序遍历（“INORDER”），前序遍历（“PREORDER”）或后序遍历（“POSTORDER”），求层序遍历。