Cho ~K~ mảng số nguyên, mỗi mảng gồm ~N~ phần tử đã được sắp xếp theo thứ tự tăng dần. Hãy gộp tất cả ~K~ mảng này thành một mảng duy nhất và vẫn đảm bảo thứ tự tăng dần.

Yêu cầu: Khối lượng dữ liệu rất lớn, nếu bạn gộp tất cả rồi mới dùng hàm sort() thì sẽ bị quá thời gian. Hãy thiết kế thuật toán sử dụng Hàng đợi ưu tiên (Priority Queue) để tối ưu.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~K~ và ~N~ (~1 \le K, N \le 500~).
• ~K~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên ~A_{i, j}~ (~-10^9 \le A_{i, j} \le 10^9~), phân cách nhau bởi khoảng trắng, đại diện cho một mảng đã được sắp xếp tăng dần.

Kết quả

In ra một dòng duy nhất chứa ~K \times N~ số nguyên của mảng sau khi đã gộp, phân cách nhau bởi một khoảng trắng.

Ví dụ

Input

3 4
1 4 7 10
2 5 8 11
3 6 9 12

Output

1 2 3 4 5 6 7 8 9 10 11 12

Giải thích

Có 3 mảng, mỗi mảng 4 phần tử. Lấy lần lượt các phần tử nhỏ nhất từ đầu các mảng ta sẽ thu được dãy tăng dần hoàn chỉnh.