Family Tree
Katya decided to display her family tree on the wall of her room. The tree is structured as follows:
The root of the tree is Katya herself.
Katya has a mom and dad, represented as the left and right subtrees, respectively.
Each person in the tree also has a mom and dad, so every node should ideally have left and right subtrees. However, Katya doesn't know all her great-great-grandparents, so some nodes might be missing one or both subtrees.
Katya hung portraits of her relatives at each node, with her own portrait at the root. It turned out beautifully!
Katya's younger brother, Anton, noticed that by simply replacing the portrait at the root, the family tree could represent his own family tree. He then thought of making the tree a shared one by placing a joint portrait of him and Katya at the root.
Since the tree was now shared, Anton decided to contribute by framing all the portraits with frames he made himself, having recently learned how to create beautiful frames in kindergarten. Anton got to work and soon had a collection of colorful frames. While Katya was away, he decided to implement his plan. He began by removing all the leaves, starting from the leftmost leaf. (A leaf is a node with no subtrees.) Anton stacked the removed portraits and took them to his room. He repeated this process until only Katya's portrait remained, which he also took.
Anton then realized, to his horror, that he couldn't reconstruct the tree from the stacks of portraits he had collected! With Katya due back from university soon, Anton feared he would be in big trouble. Help Anton restore the tree! Use the letter labels Katya marked on each tree node. Each node follows these rules:
The letters of all nodes in the left subtree precede the letter label of the current node alphabetically.
The letters of all nodes in the right subtree follow the letter label of the current node alphabetically.
The picture shows an example of the tree and the sequence of Anton's actions.
Input
The input file consists of several lines, each containing the letter labels of the removed nodes. The last line contains the symbol '*', indicating the end of the data lines.
Output
In the output file, print a line representing the structure of the tree in the following order:
If the tree is empty, the output should be empty.
If the tree is not empty, print the data in this order:
Data of the root node.
Data of the left subtree.
Data of the right subtree.
If there are multiple valid solutions, you may output any one of them.