Description

输入一棵二叉树，输出其先序遍历序列。

Format

Input

第1行为二叉树的节点数$n$ $（1≤n ≤26）$。后面的$n$ 行，以每一个字母为节点，后两个字母分别为其左、右孩子。对空节点用$*$表示。

Output

输出二叉树的先序遍历序列。

Samples

6
abc
bdi
cj*
d**
i**
j**

abdicj