Annetaan pituudeltaan $N$ oleva positiivisten kokonaislukujen jono $A=(A_1, A_2, \ldots, A_N)$ sekä pituudeltaan $M$ oleva positiivisten kokonaislukujen jono $B=(B_1, B_2, \ldots, B_M)$. Molemmat jonot ovat monotonisesti ei-väheneviä. Toisin sanoen ne toteuttavat ehdot $A_1 \le A_2 \le \cdots \le A_N$ ja $B_1 \le B_2 \le \cdots \le B_M$.

Seuraavan algoritmin avulla muodostamme näistä jonoista pituudeltaan $N+M$ olevan positiivisten kokonaislukujen jonon $C=(C_1, C_2, \ldots, C_{N+M})$:

1. Aluksi $C$ on tyhjä.
2. Jos sekä $A$ että $B$ ovat tyhjiä, lopeta.
3. Jos joko $A$ tai $B$ on tyhjä, olkoon $t$ se jono, joka ei ole tyhjä. Jos kumpikaan ei ole tyhjä, olkoon $t$ se jono, jonka ensimmäinen alkio on pienempi. Kuitenkin jos jonojen $A$ ja $B$ ensimmäiset alkiot ovat yhtä suuret, asetetaan $t$:ksi $A$.
4. Lisää jonon $t$ ensimmäinen alkio jonon $C$ perään.
5. Poista jonon $t$ ensimmäinen alkio.
6. Palaa kohtaan 2.

Kun annetaan monotonisesti ei-vähenevät positiivisten kokonaislukujen jonot $A$ ja $B$, kirjoita ohjelma, joka tulostaa tämän algoritmin muodostaman positiivisten kokonaislukujen jonon $C$.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

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

Tuloste

Tulosta vakiotulosteeseen $N + M$ riviä. Tulosta riville $k$ ($1 \le k \le N + M$) luku $C_k$.

Rajoitukset

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

Esimerkit

Syöte 1

2 1
1 2
2

Tuloste 1

1
2
2

Huomautus 1

Ennen algoritmin suorittamista $A=(1,2), B=(2)$. Jono $C$ muodostetaan seuraavasti:

• Koska jonon $A$ ensimmäinen alkio on $1$ ja jonon $B$ ensimmäinen alkio on $2$, lisätään jonon $A$ ensimmäinen alkio jonoon $C$ ja poistetaan se jonosta $A$.
• Koska jonon $A$ ensimmäinen alkio on $2$ ja jonon $B$ ensimmäinen alkio on $2$, lisätään jonon $A$ ensimmäinen alkio jonoon $C$ ja poistetaan se jonosta $A$.
• Koska jono $A$ on tyhjä, lisätään jonon $B$ ensimmäinen alkio jonoon $C$ ja poistetaan se jonosta $B$.
• Koska sekä jono $A$ että jono $B$ ovat tyhjiä, algoritmi päättyy.

Algoritmin päätyttyä jono on $C=(1,2,2)$.

Syöte 2

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

Tuloste 2

1
3
3
3
4
5
6
7
8
8
9