Problem Description

Given two digit sequences $A$ and $B$, merge $A$ and $B$ with a two-way merge to obtain a new digit sequence $T$. Find the lexicographically smallest $T$.

Input Format

The first line contains an integer $n$, the length of $A$.

The second line contains $n$ integers, representing $A$.

The third line contains an integer $m$, the length of $B$.

The fourth line contains $m$ integers, representing $B$.

Output Format

Output one line with $n + m$ positive integers, representing the lexicographically smallest $T$.

6
1 2 3 1 2 4
7
1 2 2 1 3 4 3

1 1 2 2 1 2 3 1 2 3 4 3 4

Hint

For $100\%$ of the testdata, $1 \leq n, m \leq 2 \times 10^5$, and each number in $A$ and $B$ is a positive integer not exceeding $10^3$.

• On 2023.9.10, two sets of hack testdata were added.

Translated by ChatGPT 5