Merge Sorted Lists

You are given two sorted lists of integers. Your task is to merge these two lists into a single sorted list.

The merging procedure should maintain the sorted order. For example, merging [1, 3, 5] and [2, 4, 6] results in [1, 2, 3, 4, 5, 6].

Note: The input will be provided via stdin and the output must be printed to stdout. The input format is described below.

In mathematical terms, if you have two sequences \(L_1 = [a_1, a_2, \dots, a_n]\) and \(L_2 = [b_1, b_2, \dots, b_m]\), you need to produce a sequence \(L = [c_1, c_2, \dots, c_{n+m}]\) such that \(L\) is sorted in non-decreasing order and \(L\) is the multi-set union of \(L_1\) and \(L_2\).

inputFormat

The input consists of four parts:

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

Each part is given on a separate line.

outputFormat

Output a single line containing the merged sorted list. The integers should be separated by a single space.

3
1 3 5
3
2 4 6

1 2 3 4 5 6