On vous donne une suite d'entiers strictement positifs $A=(A_1, A_2, \ldots, A_N)$ de longueur $N$ et une suite d'entiers strictement positifs $B=(B_1, B_2, \ldots, B_M)$ de longueur $M$. Ces deux suites sont croissantes au sens large. Autrement dit, elles vérifient $A_1 \le A_2 \le \cdots \le A_N$ et $B_1 \le B_2 \le \cdots \le B_M$.

À l'aide de l'algorithme suivant, on génère à partir de ces suites une suite d'entiers strictement positifs $C=(C_1, C_2, \ldots, C_{N+M})$ de longueur $N+M$ :

1. Au début, $C$ est vide.
2. Si $A$ et $B$ sont toutes les deux vides, on termine.
3. Si l'une des suites $A$ ou $B$ est vide, on note $t$ la suite non vide. Si aucune des deux n'est vide, on note $t$ la suite dont le premier élément est le plus petit. Toutefois, si les premiers éléments de $A$ et de $B$ ont la même valeur, on pose $t$ égal à $A$.
4. On ajoute le premier élément de $t$ à la fin de $C$.
5. On supprime le premier élément de $t$.
6. On retourne à l'étape 2.

Étant donné les suites d'entiers strictement positifs croissantes au sens large $A$ et $B$, écrivez un programme qui affiche la suite d'entiers strictement positifs $C$ générée par cet algorithme.

Entrée

L'entrée est fournie depuis l'entrée standard dans le format suivant :

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

Sortie

Affichez $N + M$ lignes sur la sortie standard. Sur la $k$-ième ligne ($1 \le k \le N + M$), affichez $C_k$.

Contraintes

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

Exemples

Entrée 1

2 1
1 2
2

Sortie 1

1
2
2

Note 1

Avant d'exécuter l'algorithme, $A=(1,2), B=(2)$. La suite $C$ est générée comme suit :

• Le premier élément de la suite $A$ étant $1$ et le premier élément de la suite $B$ étant $2$, on ajoute le premier élément de la suite $A$ à la suite $C$ et on le supprime de la suite $A$.
• Le premier élément de la suite $A$ étant $2$ et le premier élément de la suite $B$ étant $2$, on ajoute le premier élément de la suite $A$ à la suite $C$ et on le supprime de la suite $A$.
• La suite $A$ étant vide, on ajoute le premier élément de la suite $B$ à la suite $C$ et on le supprime de la suite $B$.
• La suite $A$ et la suite $B$ étant toutes deux vides, l'algorithme se termine.

Une fois l'algorithme terminé, la suite est $C=(1,2,2)$.

Entrée 2

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

Sortie 2

1
3
3
3
4
5
6
7
8
8
9