本题没有可用的提交语言。

描述

图1

图1显示了字母二叉树的图形表示。熟悉二叉树的人可以跳过字母二叉树、二叉树的叶子和字母二叉搜索树的定义，直接进入问题。

字母二叉树可以是以下两种情况之一：

它可以是空的。

可能存在根节点。节点以字母作为数据，并引用左子树和右子树。左子树和右子树也是字母二叉树。

在字母二叉树的图形表示中：

空树完全省略。

每个节点用

它的字母数据

如果左子树是非空的，

如果右子树是非空的，则从左子树向右的线段。

二叉树中的叶子是其子树都为空的节点。在图1的示例中，这将是包含数据B、D、H、P和y的五个节点。

如果树不为空，则预序遍历由以下内容组成：order

根节点的数据，

根的左子树的预序遍历，

根的右子树的预序遍历。

图1中树的预序遍历为$KGCBDHQMPY$。

如图1所示的树也是一个字母二叉搜索树。字母二叉搜索树是一棵每个节点都满足以下条件的字母二叉树：

根节点的数据在字母表中比左子树中所有节点的数据都晚。

根的数据在字母表中比右子树中所有节点的数据更早。

问题：

考虑以下对字母

的二叉搜索树的操作序列删除叶子并列出删除的数据

重复此过程，直到树为空

从下面左边的树开始，我们产生如下所示的树序列：然后空树

通过删除具有数据

BDHPY

CM

GQ

K

你的问题是从字母二叉搜索树的叶子行序列开始，并输出树的预排序遍历。

Input

输入将包含一个或多个数据集。每个数据集是由一行或多行大写字母组成的序列。

这些行包含在上面描述的阶段中从二叉搜索树中删除的叶子。一行中的字母将按字母递增的顺序排列。数据集由仅包含星号（'*'）的一行分隔。

最后一个数据集后面跟着一行只包含一个美元符号（'$'）。输入中没有空格或空行。

输出

对于每个输入数据集，都有一个唯一的二叉搜索树来产生叶序列。输出是一行，只包含该树的预排序遍历，没有空格。

BDHPY
CM
GQ
K
*
AC
B
$

KGCBDHQMPY
BAC

来源

美国中南部2000