Extended Binary Tree

Problem Background

Special for beginners, ^_^

Problem Description

Because none of the pre-order, in-order, or post-order sequences alone can uniquely determine a binary tree, we process the tree as follows: we pad every empty (null) node with a ., as shown in the figure.

We call the resulting tree the extended binary tree of the original one; the pre-order and post-order sequences of an extended binary tree uniquely determine the binary tree.

You are given the pre-order sequence of an extended binary tree; output its in-order and post-order sequences.

Input Format

One string, made of uppercase letters and ., giving the pre-order sequence of the extended binary tree. Its length is less than $50$.

Output Format

Print two lines: the first is the in-order sequence, the second is the post-order sequence.

Sample Input

ABD..EF..G..C..

Sample Output

DBFEGAC
DFGEBCA

Constraints

Length of the string $< 50$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• The . marks an empty subtree. In pre-order traversal, when you read a . you return (that branch is null); otherwise create the node and recurse left then right.
• Reconstruct the tree recursively, then output in-order and post-order.