Description

给出一个n个结点的二叉树，请输出二叉树的前序遍历，中序遍历和后序遍历。

Format

Input

共n+1行，第一行有一个整数 n(0<n≤26)，表示二又树有 n个结点;以下n行，每行第一个为一个大写字母，表示结点的值，第 n+1行的结点编号为n。后面为两个整数，第一个表示该结点左孩子结点编号，第二个表示该结点右孩子结点编号如果该编号为 0 0表示没有。注意:编号为1的结点是树的根。

Output

共三行，第一行为二叉树的前序遍历，第二行为中序遍历，第三行为后序遍历

Samples

7
F 2 3
C 4 5
E 0 6
A 0 0
D 7 0
G 0 0
B 0 0

FCADBEG
ACBDFEG
ABDCGEF

Limitation

1s, 1024KiB for each test case.