Cho dãy số nguyên dương \(A=(A_1,A_2,\ldots,A_N)\) có độ dài \(N\) và dãy số nguyên dương \(B=(B_1,B_2,\ldots,B_M)\) có độ dài \(M\). Cả hai dãy đều không giảm, nghĩa là \(A_1 \le A_2 \le \cdots \le A_N\) và \(B_1 \le B_2 \le \cdots \le B_M\).

Dùng thuật toán sau để tạo dãy số nguyên dương \(C=(C_1,C_2,\ldots,C_{N+M})\) có độ dài \(N+M\) từ hai dãy trên:

1. Ban đầu, \(C\) là dãy rỗng.
2. Nếu cả \(A\) và \(B\) đều rỗng thì kết thúc.
3. Nếu chỉ một trong hai dãy \(A\) và \(B\) rỗng, gọi dãy còn lại là \(t\). Nếu cả hai dãy đều không rỗng, gọi dãy có phần tử đầu nhỏ hơn là \(t\). Nếu hai phần tử đầu bằng nhau thì chọn \(t=A\).
4. Thêm phần tử đầu của \(t\) vào cuối \(C\).
5. Xóa phần tử đầu của \(t\).
6. Quay lại bước 2.

Hãy viết chương trình nhận hai dãy số nguyên dương không giảm \(A, B\) và in ra dãy \(C\) được tạo bởi thuật toán trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M

Dữ liệu ra

In ra \(N+M\) dòng. Dòng thứ \(k\) (\(1 \le k \le N+M\)) chứa \(C_k\).

Ràng buộc

• \(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\).

Ví dụ

2 1
1 2
2

1
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

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.