You are given a sequence of positive integers $A=(A_1, A_2, \ldots, A_N)$ of length $N$ and a sequence of positive integers $B=(B_1, B_2, \ldots, B_M)$ of length $M$. Both of these sequences are monotonically non-decreasing. That is, they satisfy $A_1 \le A_2 \le \cdots \le A_N$ and $B_1 \le B_2 \le \cdots \le B_M$.

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

1. Initially, let $C$ be empty.
2. If both $A$ and $B$ are empty, terminate.
3. If either $A$ or $B$ is empty, let $t$ be the sequence that is not empty. If neither is empty, let $t$ be the sequence whose first element is smaller. However, if the first elements of $A$ and $B$ have the same value, let $t$ be $A$.
4. Append the first element of $t$ to the end of $C$.
5. Remove the first element of $t$.
6. Return to step 2.

Given the monotonically non-decreasing sequences of positive integers $A$ and $B$, write a program to output the sequence of positive integers $C$ generated by this algorithm.

Input

The input is given from Standard Input in the following format:

$$ \begin{aligned} &N \ M \\ &A_1 \ A_2 \ \cdots \ A_N \\ &B_1 \ B_2 \ \cdots \ B_M \end{aligned} $$

Output

Output $N + M$ lines to Standard Output. On line $k$ ($1 \le k \le N + M$), output $C_k$.

Constraints

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

Examples

Input 1

2 1
1 2
2

Output 1

1
2
2

Note 1

Before performing the algorithm, $A=(1,2), B=(2)$. The sequence $C$ is generated as follows:

• Since the first element of sequence $A$ is $1$ and the first element of sequence $B$ is $2$, append the first element of sequence $A$ to sequence $C$ and remove it from sequence $A$.
• Since the first element of sequence $A$ is $2$ and the first element of sequence $B$ is $2$, append the first element of sequence $A$ to sequence $C$ and remove it from sequence $A$.
• Since sequence $A$ is empty, append the first element of sequence $B$ to sequence $C$ and remove it from sequence $B$.
• Since both sequence $A$ and sequence $B$ are empty, terminate the algorithm.

After the algorithm terminates, the sequence is $C=(1,2,2)$.

Input 2

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

Output 2

1
3
3
3
4
5
6
7
8
8
9