No submission language available for this problem.

Background

Special for beginners, ^_^

搜索树

https://shimo.im/docs/1lq7rGv1zbUOzX3e

平衡树

https://shimo.im/docs/KrkElY76KRCvLnqJ

Description

一棵字母二叉树如下图所示：

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

1）空树；

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

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

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

1）按字母序，根节点的数据在左子树的所有节点的数据之后；

2）根节点的数据在右子树的所有节点的节点的数据之前。

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

产出的树叶序列如下：

BDHPY
CM
GQ
K

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

Format

Input

输入包含多个测试用例。每个测试用例都是一行或多行大写字母序列，每行都给出按上述描述步骤从二叉搜索树中删除的树叶，每行给出的字母都按字母升序排列。在测试用例之间以一行分隔，该行仅包含一个星号 "*" 。在最后一个测试用例后给出一行，该行仅给出一个符号 "$" 。在输入中没有空格或空行.

Output

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

Samples

BDHPY
CM
GQ
K
*
AC
B
$

KGCBDHQMPY
BAC

Limitation

1s, 1024KiB for each test case.