Trộn hai mảng đã sắp xếp

Mô tả bài toán

Trộn hai danh sách đã sắp xếp là bước lõi của sắp xếp trộn (merge sort) và của việc hợp nhất kết quả từ nhiều nguồn. Kỹ thuật hai con trỏ cho kết quả trong O(n+m) mà không cần sắp xếp lại.

Yêu cầu

Đọc từ stdin: dòng 1 chứa n và m; dòng 2 chứa n số nguyên đã sắp xếp tăng dần; dòng 3 chứa m số nguyên đã sắp xếp tăng dần. In ra dãy gộp đã sắp xếp tăng dần, cách nhau bởi dấu cách.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không truyền lời nhắc vào input(). Lời nhắc sẽ bị in vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ n, m ≤ 10⁵; |a_i| ≤ 10⁹; cả hai dãy đã sắp xếp tăng dần.