Merge Two BST Inorder Traversals

You are given two sorted arrays representing the in-order traversal of binary search trees (BSTs). Your task is to merge these arrays into a single sorted array while maintaining the BST property.

The process can be formulated as follows: Given two sorted sequences \(A = [a_1, a_2, \ldots, a_n]\) and \(B = [b_1, b_2, \ldots, b_m]\), produce the merged sorted sequence \(C\) such that \(C\) contains all elements from both \(A\) and \(B\) in non-decreasing order. An optimal solution runs in \(O(n+m)\) time.

Note that the arrays may contain duplicate elements.

inputFormat

The input is read from standard input (stdin) and consists of four lines:

1. The first line contains an integer (n), the number of elements in the first BST's in-order traversal.
2. The second line contains (n) space-separated integers representing the first BST.
3. The third line contains an integer (m), the number of elements in the second BST's in-order traversal.
4. The fourth line contains (m) space-separated integers representing the second BST.

Note: When (n = 0) or (m = 0), the corresponding line for the BST elements will be empty.

outputFormat

Output to standard output (stdout) a single line containing the merged sorted sequence with each element separated by a single space.## sample

3
1 3 5
3
2 4 6

1 2 3 4 5 6