문제
길이 \(N\)의 양의 정수열 \(A=(A_1, A_2, \ldots, A_N)\)과 길이 \(M\)의 양의 정수열 \(B=(B_1, B_2, \ldots, B_M)\)이 주어진다. 두 수열은 모두 넓게 보면 단조 증가이다. 즉 \(A_1 \le A_2 \le \cdots \le A_N\), \(B_1 \le B_2 \le \cdots \le B_M\)을 만족한다. 다음 알고리즘으로 길이 \(N+M\)의 양의 정수열 \(C=(C_1, C_2, \ldots, C_{N+M})\)을 만든다.
넓게 보면 단조 증가인 양의 정수열 \(A\), \(B\)가 주어질 때, 이 알고리즘으로 만들어지는 양의 정수열 \(C\)를 출력하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\) \(M\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_M\)
- 첫째 줄에 정수 \(N\)과 \(M\)이 공백 하나로 구분되어 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \ldots, A_N\)이 공백 하나로 구분되어 주어진다.
- 셋째 줄에 \(M\)개의 정수 \(B_1, B_2, \ldots, B_M\)이 공백 하나로 구분되어 주어진다.
- \(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\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
\(N+M\)줄을 출력한다. \(k\)번째 줄 (\(1 \le k \le N+M\))에는 \(C_k\)를 출력한다.
예시 1
입력
2 1
1 2
2
출력
1
2
2
설명
처음 \(A=(1,2)\), \(B=(2)\)이다. \(A\)의 맨 앞 \(1\)이 \(B\)의 맨 앞 \(2\)보다 작아 \(1\)을 \(C\)에 붙인다. 다음 \(A\)와 \(B\)의 맨 앞이 모두 \(2\)이므로 \(A\)의 \(2\)를 \(C\)에 붙인다. \(A\)가 비었으므로 \(B\)의 \(2\)를 \(C\)에 붙인다. 둘 다 비어 끝나며 \(C=(1,2,2)\)이다.
예시 2
입력
3 8
1 3 8
3 3 4 5 6 7 8 9
출력
1
3
3
3
4
5
6
7
8
8
9