Description
Figure 1 shows a graphical representation of a binary tree of letters. PeZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcGxlIGZhbWlsaWFyIHdpdGggYmluYXJ5IHRyZWVzIGNhbiBza2lwIG92ZXIgdGhlIGRlZmluaXRpb25zIG9mIGEgYmluYXJ5IHRyZWUgb2YgbGV0dGVycywgbGVhdmVzIG9mIGEgYmluYXJ5IHRyZWUsIGFuZCBhIGJpbmFyeSBzZWFyY2ggdHJlZSBvZiBsZXR0ZXJzLCBhbmQgZ28gcmlnaHQgdG8gVGhlIHByb2JsZW0uCjxicj4KPGJyPgpBIGJpbmFyeSB0cmVlIG9mIGxldHRlcnMgbWF5IGJlIG9uZSBvZiB0d28gdGhpbmdzOiA8YnI+Ckl0IG1heSBiZSBlbXB0eS4gPGJyPgpJdCBtYXkgaGF2ZSBhIHJvb3Qgbm9kZS4gQSBub2RlIGhhcyBhIGxldHRlciBhcyBkYXRhIGFuZCByZWZlcnMgdG8gYSBsZWZ0IGFuZCBhIHJpZ2h0IHN1YnRyZWUuIFRoZSBsZWZ0IGFuZCByaWdodCBzdWJ0cmVlcyBhcmUgYWxzbyBiaW5hcnkgdHJlZXMgb2YgbGV0dGVycy48YnI+Cjxicj4KSW4gdGhlIGdyYXBoaWNhbCByZXByZXNlbnRhdGlvbiBvZiBhIGJpbmFyeSB0cmVlIG9mIGxldHRlcnM6IDxicj4KRW1wdHkgdHJlZXMgYXJlIG9taXR0ZWQgY29tcGxldGVseS4gPGJyPgpFYWNoIG5vZGUgaXMgaW5kaWNhdGVkIGJ5IDxicj4KSXRzIGxldHRlciBkYXRhLCA8YnI+CkEgbGluZSBzZWdtZW50IGRvd24gdG8gdGhlIGxlZnQgdG8gdGhlIGxlZnQgc3VidHJlZSwgaWYgdGhlIGxlZnQgc3VidHJlZSBpcyBub25lbXB0eSwKPGJyPgpBIGxpbmUgc2VnbWVudCBkb3duIHRvIHRoZSByaWdodCB0byB0aGUgcmlnaHQgc3VidHJlZSwgaWYgdGhlIHJpZ2h0IHN1YnRyZWUgaXMgbm9uZW1wdHkuPGJyPgo8YnI+CkEgbGVhZiBpbiBhIGJpbmFyeSB0cmVlIGlzIGEgbm9kZSB3aG9zZSBzdWJ0cmVlcyBhcmUgYm90aCBlbXB0eS4gSW4gdGhlIGV4YW1wbGUgaW4gRmlndXJlIDEsIHRoaXMgd291bGQgYmUgdGhlIGZpdmUgbm9kZXMgd2l0aCBkYXRhIEIsIEQsIEgsIFAsIGFuZCBZLgo8YnI+Cjxicj4KVGhlIHByZW9yZGVyIHRyYXZlcnNhbCBvZiBhIHRyZWUgb2YgbGV0dGVycyBzYXRpc2ZpZXMgdGhlIGRlZmluaW5nIHByb3BlcnRpZXM6IDxicj4KSWYgdGhlIHRyZWUgaXMgZW1wdHksIHRoZW4gdGhlIHByZW9yZGVyIHRyYXZlcnNhbCBpcyBlbXB0eS4gPGJyPgpJZiB0aGUgdHJlZSBpcyBub3QgZW1wdHksIHRoZW4gdGhlIHByZW9yZGVyIHRyYXZlcnNhbCBjb25zaXN0cyBvZiB0aGUgZm9sbG93aW5nLCBpbiBvcmRlcgo8YnI+ClRoZSBkYXRhIGZyb20gdGhlIHJvb3Qgbm9kZSwgPGJyPgpUaGUgcHJlb3JkZXIgdHJhdmVyc2FsIG9mIHRoZSByb290"s left subtree,
The preorder traversal of the root's right subtree.
The preorder traversal of the tree in Figure 1 is KGCBDHQMPY.
A tree like the one in Figure 1 is also a binary search tree of letters. A binary search tree of letters is a binary tree of letters in which each node satisfies:
The root's data comes later in the alphabet than all the data in the nodes in the left subtree.
The root's data comes earlier in the alphabet than all the data in the nodes in the right subtree.
The problem:
Consider the following sequence of operations on a binary search tree of letters
Remove the leaves and list the data removed
Repeat this procedure until the tree is empty
Starting from the tree below on the left, we produce the sequence of trees shown, and then the empty tree
BDHPY
CM
GQ
K
Your problem is to start with such a sequence of lines of leaves from a binary search tree of letters and output the preorder traversal of the tree.
Input
The input will contain one or more data sets. Each data set is a sequence of one or more lines of capital letters.The lines contain the leaves removed from a binary search tree in the stages described above. The letters on a line will be listed in increasing alphabetical order. Data sets are separated by a line containing only an asterisk ('*').
The last data set is followed by a line containing only a dollar sign ('$'). There are no blanks or emp