Problem Description

Given two sequences of positive integers of length $N$, $A=(A_1, A_2, \ldots, A_N)$, and of length $M$, $B=(B_1, B_2, \ldots, B_M)$, both of which are non-decreasing sequences. That is, $A_1 \leq A_2 \leq \cdots \leq A_N$ and $B_1 \leq B_2 \leq \cdots \leq B_M$.

Using the following algorithm, generate a sequence of positive integers $C=(C_1, C_2, \ldots, C_{N+M})$ from these sequences:

1. Initially, $C$ is empty.
2. If both $A$ and $B$ are empty, terminate the process.
3. If one of $A$ or $B$ is empty, let $t$ be the non-empty sequence. If both are non-empty, let $t$ be the sequence with the smaller leading element. If the leading elements of $A$ and $B$ are equal, let $t$ be $A$.
4. Append the leading element of $t$ to the end of $C$.
5. Remove the leading element of $t$.
6. Go back to step 2.

Write a program that outputs the sequence $C$ generated by this algorithm when given non-decreasing sequences $A$ and $B$.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$

Output Format

Output $N + M$ lines to the standard output.

The $k$-th line ($1 \leq k \leq N + M$) should contain $C_k$.

Sample Input and Output

Sample Input #1

2 1
1 2
2

Sample Output #1

1
2
2

Sample Input #2

3 8
1 3 8
3 3 4 5 6 7 8 9

Sample Output #2

1
3
3
3
4
5
6
7
8
8
9

Notes/Hints

Constraints

• $1 \leq N \leq 500$.
• $1 \leq M \leq 500$.
• $1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 2000$.
• $1 \leq B_1 \leq B_2 \leq \cdots \leq B_M \leq 2000$.

Sample Explanation 1

Before starting the algorithm, $A=(1,2)$ and $B=(2)$. The sequence $C$ is generated as follows:
- The leading element of sequence $A$ is $1$, and the leading element of sequence $B$ is $2$, so append the leading element of sequence $A$ to sequence $C$ and remove it from sequence $A$.
- The leading element of sequence $A$ is $2$, and the leading element of sequence $B$ is $2$, so append the leading element of sequence $A$ to sequence $C$ and remove it from sequence $A$.
- Sequence $A$ is empty, so append the leading element of sequence $B$ to sequence $C$ and remove it from sequence $B$.
- Both sequences $A$ and $B$ are empty, so terminate the algorithm.
After the algorithm terminates, the sequence $C=(1,2,2)$.

见题面 Input 部分

见题面 Output 部分