Drawing a Binary Tree

Problem Background

Special for beginners, ^_^

Problem Description

The "recessed" representation of a tree is mainly used for screen or printed output. Its basic idea: siblings are drawn with equal length, and a node's length must be at least the sum of its children's lengths. A binary tree can be drawn this way too: assume a leaf has length $1$, and a non-leaf node's length equals the sum of its left and right subtree lengths.

Each node of a binary tree is described by one letter (no duplicates). When printing, start from the root:

• Each line prints several copies of the node's letter (the count equals the node's length).
• If the node has a left subtree, recursively print the left subtree.
• If the node has a right subtree, recursively print the right subtree.

Given the pre-order and in-order traversal strings of a binary tree, output that binary tree using the recessed representation.

Input Format

Two lines in total, each a string of letters (all characters on a line are distinct), giving the pre-order and in-order traversal sequences of the binary tree. Each string's length is less than $50$.

Output Format

The number of output lines equals the number of nodes in the tree; each line consists of identical letters.

Sample Input

ABCDEFG
CBDAFEG

Sample Output

AAAA
BB
C
D
EE
F
G

Constraints

Length of each string $< 50$.

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

Hint

• Reconstruct the tree from pre-order + in-order first.
• Compute each node's length: leaf → $1$, internal → leftLen + rightLen. Then print letter repeated length times for the current node, then recurse left, then recurse right.