题目描述

输入一串二叉树，输出其前序遍历。

输入格式

二叉树的前序遍历。 一行是二叉树的结点数n(1≤n≤26)。 接下来n行,每行3个小写字符。第一个字母表示为结点,后两个字母分别是其左右儿子。若 孩子结点是空结点,用*代替。注意：数据第一行结点是根结点。

输出格式

二叉树的前序遍历。

样例

输入样例 1

6
bfc
fdi
c**
dj*
i**
j**

输出样例 1

bfdjic

输入样例 2

1
a**

输出样例 2

a

输入样例 3

8
abc
bef
cd*
d*h
e**
fg*
g**
h**

输出样例 3

abefgcdh