Background

Special for beginners, ^_^

Description

输入一棵普通有序树，输出该树的前序和后序次序。

Format

Input

顶点个数n(1<=n<=200) 以下含n行，其中第i行（1<=i<=n)的元素依此为结点的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。

Output

输出两行，分别为普通有序树的前序和后序次序

Samples

4
A 2 3 4 0
B 0
C 0
D 0

ABCD
DCBA

Limitation

1s, 1024KiB for each test case.