## Task Description

This task is to build a tree from two linked lists. Every node of the two linked lists has a distinct integer value and two pointers, left and right. Initially, the left pointer of a node points to the next node in the linked list, and the right pointer is NULL.

Now we define how to split a linked list of $n$ nodes into two halves. If $n$ is even, then the first half has the first $n/2$ nodes of the list, and the second half has $n/2$ nodes of the list. If $n$ is odd, then the first half has of the first $(n+1)/2$ node of the list, and the second half has $(n-1)/2$ nodes of the list.

Here is a recursive definition to build a tree $T$ from two linked lists $L$ and $R$.

- If both $L$ and $R$ are not NULL, then we compare the value of the head of two linked lists, and the smaller one is the root of $T$. We then recursively build the left subtree of $T$ from the two
*first*halves of the remaining $L$ and $R$, and recursively build the right subtree from the two*second*halves of remaining $L$ and $R$. - If either $L$ or $R$ is NULL, then the tree is the non-NULL one of $L$ or $R$. That is, all the nodes in the tree are in the left subtree.
- If both $L$ and $R$ are NULL, the tree is NULL.

Note that you can only use the list nodes given to you, and you *cannot* allocate any large amount of memory.

Please refer to the following figure for an illustration.

You have to do it in a function, BuildTree. The arguments of BuildTree are two pointers, and each of them points to a linked list. The return value is the root of the tree.
The following is `BuildTree.h`

file.

`typedef`

`struct`

`Node`

`{`

` `

`int`

`val;`

` `

`struct`

`Node *left, *right;`

`}Node;`

`Node* BuildTree(Node* list1, Node* list2);`

You can test your function with this main function.

`#include <stdio.h>`

`#include "BuildTree.h"`

`#define MAXN 100`

`void`

`tree_print(Node* root){`

` `

`if`

`(root == NULL) `

`return`

`;`

` `

`printf`

`(`

`"%d "`

`, root->val);`

` `

`tree_print(root->left);`

` `

`tree_print(root->right);`

`}`

`int`

`main()`

`{`

` `

`int`

`i, n, m, num;`

` `

`Node l1[MAXN], l2[MAXN];`

` `

`scanf`

`(`

`"%d%d"`

`, &n, &m);`

` `

`for`

`(i = 0; i < n; i++){`

` `

`scanf`

`(`

`"%d"`

`, &num);`

` `

`l1[i].val = num;`

` `

`l1[i].left = &l1[i+1];`

` `

`l1[i].right = NULL;`

` `

`}`

` `

`l1[n-1].left = NULL;`

` `

`Node *root1 = &l1[0];`

` `

`for`

`(i = 0; i < m; i++){`

` `

`scanf`

`(`

`"%d"`

`, &num);`

` `

`l2[i].val = num;`

` `

`l2[i].left = &l2[i+1];`

` `

`l2[i].right = NULL;`

` `

`}`

` `

`l2[m-1].left = NULL;`

` `

`Node *root2 = &l2[0];`

` `

`Node *ans = BuildTree(root1, root2);`

` `

`tree_print(ans);`

` `

`printf`

`(`

`"\n"`

`);`

` `

`return`

`0;`

`}`

## Input Format

The first line has two integers, n and m. They are the lengths of two linked list. The second line has n integers, which are the values of the first linked list. The third line has m integers, which are the values of the second linked list.

## Output Format

Output the preorder of the tree.

## Sample Input 1

`3 4`

`4 7 0`

`6 9 5 3`

## Sample Output 1

`4 6 7 9 0 5 3`

## Sample Input 2

`3 7`

`8 11 1`

`4 5 3 9 13 2 7`

## Sample Output 2

`4 5 3 8 9 11 1 13 2 7`