题目描述

一棵字母二叉树如下图所示。熟悉二叉树的读者可以跳过字母二叉树、二叉树树叶和字母二叉搜索树的定义，直接看问题描述。

一棵字母二叉树可以是两者之一：

1. 空树。
2. 有一个根节点，每个节点都以一个字母作为数据，并且有指向左子树和右子树的指针，左右子树也是字母二叉树。

二叉树的树叶是一个左右子树都为空的节点。在上图的实例中有 $5$ 个树叶节点，分别为 $B$、$D$、$H$、$P$ 和 $Y$。

字母二叉搜索树是每个节点满足下述条件的字母二叉树：

1. 按字母序，根节点的数据在左子树的所有节点的数据之后。
2. 根节点的数据在右子树的所有节点的数据之前。

在一棵字母二叉搜索树上删除树叶，并将被删除的树叶列出；重复这一过程，直到树为空。例如，从左边的树开始，产生树的序列如下图所示，最后产生空树。

删除的树叶序列如下：

BDHPY
CM
GQ
K

给定一个字母二叉搜索树的树叶删除序列，输出树的先序遍历。

输入格式

输入包含多个测试用例。每个测试用例都是一行或多行大写字母序列，每行都给出按上述描述步骤从二叉搜索树中删除的树叶，每行给出的字母都按字母升序排列。

在测试用例之间以一行分隔，该行仅包含一个星号 *。在最后一个测试用例后给出一行，该行仅给出一个符号 $。在输入中没有空格或空行。

输出格式

对于每个测试用例，都有唯一的二叉搜索树，单行输出该树的先序遍历。

样例

BDHPY
CM
GQ
K
*
AC
B
$

KGCBDHQMPY
BAC

样例分析

如上所述。

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le n \leq 100$。