Insert New Books

You are given two lists. The first list contains the heights of books already arranged in non-decreasing order, and the second list contains new books (which may not be sorted). Your task is to insert the new books into the existing list such that the final list remains sorted in non-decreasing order.

This can be formulated as follows: Given two sequences \(L_1\) (sorted) and \(L_2\), output the merged list \(L\) where

[ L = \text{sorted}(L_1 \cup L_2) ]

For example, if \(L_1 = [3, 5, 7, 9, 11]\) and \(L_2 = [4, 6, 8]\), the merged list is \( [3, 4, 5, 6, 7, 8, 9, 11] \).

inputFormat

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

1. An integer \(n\) representing the number of existing books.
2. \(n\) space-separated integers representing the heights of the existing books, given in non-decreasing order.
3. An integer \(m\) representing the number of new books.
4. \(m\) space-separated integers representing the heights of the new books (order may not be sorted).

Note: In case \(n = 0\) or \(m = 0\), the corresponding list of numbers will be empty.

outputFormat

Output a single line to standard output (stdout) containing the merged list of book heights in non-decreasing order. The numbers should be space-separated.

5
3 5 7 9 11
3
4 6 8

3 4 5 6 7 8 9 11