Gegeben sind eine Folge positiver ganzer Zahlen $A=(A_1, A_2, \ldots, A_N)$ der Länge $N$ und eine Folge positiver ganzer Zahlen $B=(B_1, B_2, \ldots, B_M)$ der Länge $M$. Beide Folgen sind monoton nichtfallend. Das heißt, sie erfüllen $A_1 \le A_2 \le \cdots \le A_N$ und $B_1 \le B_2 \le \cdots \le B_M$.

Mit dem folgenden Algorithmus erzeugen wir aus diesen Folgen eine Folge positiver ganzer Zahlen $C=(C_1, C_2, \ldots, C_{N+M})$ der Länge $N+M$:

1. Zu Beginn sei $C$ leer.
2. Falls sowohl $A$ als auch $B$ leer sind, beende den Algorithmus.
3. Falls entweder $A$ oder $B$ leer ist, sei $t$ die nicht leere Folge. Falls beide nicht leer sind, sei $t$ die Folge, deren erstes Element kleiner ist. Haben jedoch die ersten Elemente von $A$ und $B$ denselben Wert, so sei $t$ gleich $A$.
4. Füge das erste Element von $t$ am Ende von $C$ an.
5. Entferne das erste Element von $t$.
6. Kehre zu Schritt 2 zurück.

Schreiben Sie ein Programm, das für gegebene monoton nichtfallende Folgen positiver ganzer Zahlen $A$ und $B$ die durch diesen Algorithmus erzeugte Folge positiver ganzer Zahlen $C$ ausgibt.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

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

Ausgabe

Geben Sie $N + M$ Zeilen auf der Standardausgabe aus. Geben Sie in der $k$-ten Zeile ($1 \le k \le N + M$) den Wert $C_k$ aus.

Bedingungen

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

Beispiele

Eingabe 1

2 1
1 2
2

Ausgabe 1

1
2
2

Hinweis 1

Vor der Ausführung des Algorithmus gilt $A=(1,2), B=(2)$. Die Folge $C$ wird wie folgt erzeugt:

• Da das erste Element der Folge $A$ gleich $1$ und das erste Element der Folge $B$ gleich $2$ ist, wird das erste Element der Folge $A$ an die Folge $C$ angehängt und aus der Folge $A$ entfernt.
• Da das erste Element der Folge $A$ gleich $2$ und das erste Element der Folge $B$ gleich $2$ ist, wird das erste Element der Folge $A$ an die Folge $C$ angehängt und aus der Folge $A$ entfernt.
• Da die Folge $A$ leer ist, wird das erste Element der Folge $B$ an die Folge $C$ angehängt und aus der Folge $B$ entfernt.
• Da sowohl Folge $A$ als auch Folge $B$ leer sind, wird der Algorithmus beendet.

Nach Beendigung des Algorithmus lautet die Folge $C=(1,2,2)$.

Eingabe 2

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

Ausgabe 2

1
3
3
3
4
5
6
7
8
8
9