Description

给出一个二叉搜索树序列，请输出它的前序遍历。

Input

输入有多组
每组输入数据仅有一行，表示一个序列，序列长度小于等于26，只会包含(a~z)的小写字母，序列中没有重复字母，根据这个序列可以构造出一颗二叉搜索树。

Output

输出这棵二叉搜索树的前序遍历序列。

Sample Input

bcasdk

Sample Output

bacsdk

HINT

Source

NBU OJ