Merge Two Sorted Linked Lists

You are given two sorted linked lists. Your task is to merge these two lists into one sorted linked list and print the result. The resulting merged list must also be sorted in non-decreasing order.

Input Format: The input consists of two parts. The first part describes the first linked list and the second describes the second linked list. For each list, the first integer denotes the number of elements in the list, followed by that many integers indicating the values stored in the list.

Output Format: Print the elements of the merged sorted linked list on one line, separated by spaces.

Example:

If the first list is [1, 3, 5] and the second list is [2, 4, 6, 8], then the merged list is 1 2 3 4 5 6 8.

The problem may include duplicate values. Ensure that your solution efficiently handles all edge cases.

inputFormat

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

1. An integer n representing the number of elements in the first sorted linked list.
2. n space-separated integers representing the elements of the first list.
3. An integer m representing the number of elements in the second sorted linked list.
4. m space-separated integers representing the elements of the second list.

You can assume that 0 <= n, m <= 10⁵ and that each list is already sorted in non-decreasing order.

outputFormat

Output a single line to stdout containing the merged sorted linked list. The numbers should be separated by a single space.

## sample

3
1 3 5
4
2 4 6 8

1 2 3 4 5 6 8