Merge Sorted Lists

You are given two lists of integers, each sorted in ascending order. Your task is to merge these two lists into a single list, which must also be sorted in ascending order.

The problem can be formally stated as follows:

Given two lists \(L_1\) and \(L_2\) where \[ L_1 = [a_1, a_2, \dots, a_n]\quad \text{and} \quad L_2 = [b_1, b_2, \dots, b_m], \] with \(a_1 \le a_2 \le \dots \le a_n\) and \(b_1 \le b_2 \le \dots \le b_m\), output a new list \(L\) such that \[ L = L_1 \cup L_2 = [c_1, c_2, \dots, c_{n+m}]\quad \text{with}\quad c_1 \le c_2 \le \dots \le c_{n+m}. \]

The expected time complexity is \(O(n+m)\) by taking advantage of the fact that the individual lists are already sorted.

inputFormat

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

• Line 1: An integer \(N\), the number of elements in the first list.
• Line 2: \(N\) space-separated integers representing the first sorted list. If \(N = 0\), this line may be empty.
• Line 3: An integer \(M\), the number of elements in the second list.
• Line 4: \(M\) space-separated integers representing the second sorted list. If \(M = 0\), this line may be empty.

outputFormat

Output to stdout a single line containing the merged sorted list. The numbers should be space-separated. There should be no extra spaces at the beginning or end of the line.

## sample

3
1 3 5
3
2 4 6

1 2 3 4 5 6

</p>