Sono date una sequenza di interi positivi $A=(A_1, A_2, \ldots, A_N)$ di lunghezza $N$ e una sequenza di interi positivi $B=(B_1, B_2, \ldots, B_M)$ di lunghezza $M$. Entrambe queste sequenze sono monotonamente non decrescenti. Cioè, soddisfano $A_1 \le A_2 \le \cdots \le A_N$ e $B_1 \le B_2 \le \cdots \le B_M$.

Utilizzando il seguente algoritmo, generiamo da queste sequenze una sequenza di interi positivi $C=(C_1, C_2, \ldots, C_{N+M})$ di lunghezza $N+M$:

1. Inizialmente, sia $C$ vuota.
2. Se sia $A$ che $B$ sono vuote, termina.
3. Se una tra $A$ e $B$ è vuota, sia $t$ la sequenza non vuota. Se nessuna delle due è vuota, sia $t$ la sequenza il cui primo elemento è più piccolo. Tuttavia, quando i primi elementi di $A$ e di $B$ hanno lo stesso valore, si pone $t$ uguale ad $A$.
4. Aggiungi il primo elemento di $t$ in coda a $C$.
5. Rimuovi il primo elemento di $t$.
6. Torna al passo 2.

Date le sequenze di interi positivi monotonamente non decrescenti $A$ e $B$, scrivi un programma che stampi la sequenza di interi positivi $C$ generata da questo algoritmo.

Input

L'input è fornito dallo standard input nel seguente formato:

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

Output

Stampa $N + M$ righe sullo standard output. Sulla $k$-esima riga ($1 \le k \le N + M$), stampa $C_k$.

Vincoli

• $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$.

Esempi

Input 1

2 1
1 2
2

Output 1

1
2
2

Note 1

Prima di eseguire l'algoritmo, $A=(1,2), B=(2)$. La sequenza $C$ viene generata come segue:

• Poiché il primo elemento della sequenza $A$ è $1$ e il primo elemento della sequenza $B$ è $2$, si aggiunge il primo elemento della sequenza $A$ alla sequenza $C$ e lo si rimuove dalla sequenza $A$.
• Poiché il primo elemento della sequenza $A$ è $2$ e il primo elemento della sequenza $B$ è $2$, si aggiunge il primo elemento della sequenza $A$ alla sequenza $C$ e lo si rimuove dalla sequenza $A$.
• Poiché la sequenza $A$ è vuota, si aggiunge il primo elemento della sequenza $B$ alla sequenza $C$ e lo si rimuove dalla sequenza $B$.
• Poiché sia la sequenza $A$ sia la sequenza $B$ sono vuote, l'algoritmo termina.

Al termine dell'algoritmo, la sequenza è $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