Bạn đã nghe đến công ty Just Odd Inventions, Ltd. chưa? Công ty này nổi tiếng với những phát minh kỳ lạ. Trong bài toán này, ta gọi công ty là JOI.

Công ty JOI đang tổ chức tiệc năm mới. Các nhân viên nướng \(N\) miếng thịt băm trên một vỉ nướng khổng lồ. Coi vỉ nướng là một bảng ô vuông kích thước \(10^9 \times 10^9\). Ký hiệu \((x,y)\) là ô ở cột thứ \(x\) từ trái sang và hàng thứ \(y\) từ dưới lên, với \(1 \le x,y \le 10^9\).

Các miếng thịt được đánh số từ \(1\) đến \(N\). Miếng thứ \(i\) (\(1 \le i \le N\)) nằm trên vùng hình chữ nhật có góc dưới bên trái là \((L_i,D_i)\) và góc trên bên phải là \((R_i,U_i)\). Các miếng thịt có thể chồng lên nhau.

Bạn là nhân viên mới của công ty JOI. Nhiệm vụ của bạn là chọn \(K\) ô trên vỉ và cắm các que tre vào tâm những ô đó, vuông góc với mặt vỉ. Để kiểm tra độ chín của một miếng thịt, phải có ít nhất một que được cắm vào một ô thuộc miếng thịt đó. Bạn cần kiểm tra tất cả các miếng thịt. Có thể cắm nhiều que vào cùng một ô, và cũng có thể cắm que vào một ô không có miếng thịt nào.

Cụ thể, hãy tìm \(K\) cặp số nguyên \((x_1,y_1),\ldots,(x_K,y_K)\), không nhất thiết đôi một khác nhau, thỏa mãn:

• Với mỗi \(i\) (\(1 \le i \le N\)), tồn tại \(j\) (\(1 \le j \le K\)) sao cho đồng thời \(L_i \le x_j \le R_i\) và \(D_i \le y_j \le U_i\).
• Với mỗi \(j\) (\(1 \le j \le K\)), có \(1 \le x_j \le 10^9\) và \(1 \le y_j \le 10^9\).

Hãy viết chương trình nhận vị trí các miếng thịt và số que tre, rồi tìm một cách cắm que thỏa mãn yêu cầu. Dữ liệu bảo đảm luôn tồn tại một cách chọn \(K\) ô như vậy.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N K
L_1 D_1 R_1 U_1
L_2 D_2 R_2 U_2
...
L_N D_N R_N U_N

Dữ liệu ra

In ra \(K\) dòng. Dòng thứ \(j\) (\(1 \le j \le K\)) chứa hai số \(x_j\) và \(y_j\), cách nhau bởi một dấu cách.

Nếu có nhiều cách cắm que thỏa mãn yêu cầu, có thể in ra một cách bất kỳ.

Ràng buộc

• \(1 \le N \le 200000\).
• \(1 \le K \le 4\).
• \(1 \le L_i \le R_i \le 10^9\) với mọi \(1 \le i \le N\).
• \(1 \le D_i \le U_i \le 10^9\) với mọi \(1 \le i \le N\).
• Luôn tồn tại \(K\) ô thỏa mãn các điều kiện trong đề bài.

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm. Các ràng buộc bổ sung và số điểm của từng nhóm như sau:

1. \(1\) điểm: \(N \le 2000\) và \(K=1\).
2. \(1\) điểm: \(N \le 2000\) và \(K=2\).
3. \(3\) điểm: \(N \le 2000\) và \(K=3\).
4. \(6\) điểm: \(N \le 2000\) và \(K=4\).
5. \(1\) điểm: \(K=1\).
6. \(3\) điểm: \(K=2\).
7. \(6\) điểm: \(K=3\).
8. \(79\) điểm: \(K=4\).

Ví dụ

4 2
2 1 3 3
1 2 4 3
6 1 7 4
5 3 7 5

2 2
7 4

3 3
1 1 1 1
1 2 1 2
1 3 1 3

1 1
1 2
1 3

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, kỳ trại huấn luyện mùa xuân JOI 2019/2020, ngày thi thứ nhất (20/03/2020). Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.