병합

문제

길이가 $N$ 인 양의 정수열 $A=(A_{1}, A_{2}, ..., A_{N})$ 과 길이가 $M$ 인 양의 정수열 $B=(B_{1}, B_{2}, ..., B_{M})$ 이 주어진다. 이 두 수열은 모두 넓은 의미에서 단조 증가하는 수열이다. 즉, $A_{1} \le A_{2} \le \dots \le A_{N}$, $B_{1} \le B_{2} \le \dots \le B_{M}$ 을 만족한다.

다음 알고리즘을 이용하여, 이 수열들로부터 길이가 $N+M$ 인 양의 정수열 $C=(C_{1}, C_{2}, ..., C_{N+M})$ 을 생성한다.

1. 처음에 $C$ 는 비어 있다.
2. $A$ 와 $B$ 가 모두 비어 있으면 종료한다.
3. $A$ 와 $B$ 중 하나가 비어 있으면, 비어 있지 않은 수열을 $t$ 라고 하자. 둘 다 비어 있지 않으면, 맨 앞의 원소가 더 작은 수열을 $t$ 라고 하자. 단, $A$ 와 $B$ 의 맨 앞의 원소가 같은 값일 때는 $A$ 를 $t$ 라고 하자.
4. $t$ 의 맨 앞의 원소를 $C$ 의 맨 뒤에 추가한다.
5. $t$ 의 맨 앞의 원소를 삭제한다.
6. 1. 로 돌아간다.

넓은 의미에서 단조 증가하는 양의 정수열 $A$, $B$ 가 주어졌을 때, 이 알고리즘으로 생성되는 양의 정수열 $C$ 를 출력하는 프로그램을 작성하시오.

제한

• $1 \le N \le 500$.
• $1 \le M \le 500$.
• $1 \le A_{1} \le A_{2} \le \dots \le A_{N} \le 2000$.
• $1 \le B_{1} \le B_{2} \le \dots \le B_{M} \le 2000$.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $M$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$B_{1}$ $B_{2}$ $\dots$ $B_{M}$

출력

표준 출력에 $N + M$ 줄을 출력한다.
$k$ 번째 줄 ($1 \le k \le N + M$) 에는 $C_{k}$ 를 출력한다.

예제 입력 1

2 1
1 2
2

예제 출력 1

1
2
2

알고리즘을 수행하기 전, $A=(1,2), B=(2)$ 이다. 다음과 같이 수열 $C$ 가 생성된다.

• 수열 $A$ 의 맨 앞의 원소는 $1$, 수열 $B$ 의 맨 앞의 원소는 $2$ 이므로, 수열 $A$ 의 맨 앞의 원소를 수열 $C$ 에 추가하고 이를 수열 $A$ 에서 삭제한다.
• 수열 $A$ 의 맨 앞의 원소는 $2$, 수열 $B$ 의 맨 앞의 원소는 $2$ 이므로, 수열 $A$ 의 맨 앞의 원소를 수열 $C$ 에 추가하고 이를 수열 $A$ 에서 삭제한다.
• 수열 $A$ 가 비어 있으므로, 수열 $B$ 의 맨 앞의 원소를 수열 $C$ 에 추가하고 이를 수열 $B$ 에서 삭제한다.
• 수열 $A$ 도 수열 $B$ 도 비어 있으므로, 알고리즘을 종료한다.

알고리즘이 종료된 후, 수열 $C=(1,2,2)$ 이다.

예제 입력 2

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

예제 출력 2

1
3
3
3
4
5
6
7
8
8
9