Family Tree

Katya decided to display her family tree on the wall of her room. The tree has the following structure:

• The root of the tree is Katya herself.

• Katya has a mother and a father, which are the left and right subtrees, respectively.

• Each person in the tree also has a mother and a father, so every node should ideally have left and right subtrees. However, Katya does not know all of her great-great-grandparents, so some nodes may be missing one or both subtrees.

Katya hung portraits of her relatives at each node, placing her own portrait at the root. It turned out beautifully!

Katya's younger brother Anton realized that the tree could represent his own family tree if only the portrait at the root was changed. After some thought, he decided to use a joint portrait of himself and Katya at the root, making the tree shared.

Since the tree was now shared, Anton decided to add his own touch by framing all the portraits with frames he had made himself. Recently, he had learned how to make beautiful frames in kindergarten. He soon had enough colorful frames. While Katya was away, Anton decided to put his plan into action. He started by removing all the leaves, beginning from the leftmost one. (A leaf is a node with no subtrees.) The removed portraits were stacked and taken to his room. He repeated the process until only Katya's portrait remained, which he also took to his room.

At that moment, Anton realized, to his horror, that he could not reconstruct the tree from the portrait stacks he had collected! Katya would soon return from university, and 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 satisfies the following conditions:

• The labels of all nodes in the left subtree come before the label of the current node alphabetically.

• The labels of all nodes in the right subtree come after the label of the current node alphabetically.

The picture shows an example of the tree and the sequence of Anton's actions.