Add Two Binary Trees (Level-Order Representation)

You are given two binary trees represented by level-order traversal arrays. In these arrays, a node with value -1 represents a null (missing) node. Your task is to add the two binary trees node by node.

The addition is defined as follows:

• If both corresponding nodes are non-null, replace the node with the sum of their values.
• If one node is null (i.e. has value -1), use the value of the non-null node.
• If both nodes are null, the result remains -1.

Note that if the trees have different sizes, extend the smaller tree with -1 values until both trees have the same number of elements.

The binary trees are provided as arrays in level-order. You must process several test cases where each test case consists of two such arrays.

Mathematical formulation:

Let \( t1 = [a_0, a_1, \dots, a_{n-1}] \) and \( t2 = [b_0, b_1, \dots, b_{n-1}] \) (after extension) where a value of \(-1\) indicates a null node. Then the resultant tree \( t = [c_0, c_1, \dots, c_{n-1}] \) is defined by

[ c_i = \begin{cases} a_i + b_i, & \text{if } a_i \neq -1 \text{ and } b_i \neq -1, \ a_i, & \text{if } a_i \neq -1 \text{ and } b_i = -1, \ b_i, & \text{if } a_i = -1 \text{ and } b_i \neq -1, \ -1, & \text{if } a_i = -1 \text{ and } b_i = -1. \end{cases} ]

inputFormat

The first line of input contains an integer T, the number of test cases.

Each test case consists of four lines:

1. An integer N indicating the number of nodes in the first binary tree.
2. N space-separated integers representing the level-order traversal of the first tree.
3. An integer M indicating the number of nodes in the second binary tree.
4. M space-separated integers representing the level-order traversal of the second tree.

Input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the result of the addition of the two binary trees. The nodes should be printed as space-separated integers in the order of their level-order traversal.

Output is written to standard output (stdout).

## sample

2
3
4 -1 3
3
5 6 -1
2
1 1
2
9 9

9 6 3
10 10

</p>