Sum of trees P18593

We define the sum of two trees as the tree that is obtained adding the values of the nodes, overlapping the children of each subtree from the left to the right.

(To see an instance with the trees corresponding to the input-output instance, consult the pdf or ps version of this wording.)

Write a program that prints the preorder traversal of the sum of two given trees.

Input

Input consists of the description of two general trees of natural numbers, as is explained at the exercise .

Output

Your program must print a line with the preorder traversal of the sum of the two trees. Each element must be preceded of a space.