问题描述

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

格式

输入

第一行为二叉树的节点数 n。(1≤n≤26)

后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。

空节点用 * 表示

输出

二叉树的前序遍历。

Samples

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

bfdjic

Limitation

1s, 1024KiB for each test case.