Background

Special for beginners, ^_^

Description

输入一棵结点数为n(1<=n<=20)的二叉树，输出该树前序遍历次序和后序遍历次序。

Format

Input

第一行结点个数n(1<=n<=20) 第二行至n+1行为个结点的信息，每行三个元素，之间用空格隔开，分别表示某结点的数据值（用一个大写字母表示）、左儿子结点编号、右儿子结点编号，若没有儿子用0表示。

Output

两行，分别为该树前序遍历次序和后序遍历次序。

Samples

3
A 2 0
B 0 3
C 0 0

ABC
CBA

Limitation

1s, 1024KiB for each test case.