Background

Special for beginners, ^_^

Description

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

熟悉二叉树的读者可以跳过字母二叉树、二叉树树叶和字母二叉搜索树的定义，直接看问题描述。 一棵字母二叉树可以是两者之一：①空树；②有一个根节点，每个节点都以一个字母作为数据，并且有指向左子树和右子树的指针，左右子树也是字母二叉树。

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

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

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

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

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

Format

Input

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

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

Output

One integer, the sum of x and y.

Samples

BDHPY
CM
GQ
K
*
AC
B
$

KGCBDHQMPY
BAC

来源

POJ1577 or UVA1525