Một người leo núi sống trên một hòn đảo nhiều núi đã lên tới một đỉnh và muốn đi tiếp đến một đỉnh cao hơn.

Mỗi điểm trên đảo có độ cao dương so với mực nước biển, còn mặt biển có độ cao \(0\). Nếu đỉnh hiện tại có độ cao \(E_i\), người leo núi muốn tới một đỉnh có độ cao \(E_j>E_i\). Vì đang đứng trên một đỉnh, anh không thể đi thẳng lên cao hơn mà trước hết phải đi xuống rồi mới leo lên. Anh muốn chọn đường đi sao cho độ cao của điểm thấp nhất trên đường đi là lớn nhất có thể.

Trong hình, nếu bắt đầu từ đỉnh có độ cao \(E_4\), anh có thể tới một trong ba đỉnh cao hơn là \(E_5,E_6,E_7\). Đường tới \(E_7\) là lựa chọn tốt nhất: anh không phải xuống thấp hơn \(E_2\), trong khi các lựa chọn còn lại buộc anh xuống tới \(E_1\). Nếu bắt đầu từ \(E_5\), độ cao thấp nhất tốt nhất là \(E_3\) trên đường tới \(E_6\); nếu bắt đầu từ \(E_6\), giá trị tương ứng là \(E_1\).

Bản đồ đảo là một bảng chữ nhật gồm \(N \times M\) ô vuông. Số ghi trong mỗi ô là độ cao của vùng tương ứng. Hai ô được coi là kề nhau nếu chúng có một điểm chung; vì thế, một ô không nằm ở biên có tám ô kề. Một đường đi là một dãy ô mà hai ô liên tiếp luôn kề nhau.

Một vùng bằng phẳng là một tập gồm một hoặc nhiều ô cùng độ cao, trong đó hai ô bất kỳ được nối với nhau bằng một đường đi chỉ qua các ô của tập. Hai ô kề nhau có cùng độ cao luôn thuộc cùng một vùng bằng phẳng. Một đỉnh là một vùng bằng phẳng mà không ô nào của vùng kề với một ô cao hơn.

Hãy tìm tất cả các đỉnh trên đảo. Với mỗi đỉnh, hãy xác định độ cao lớn nhất có thể của điểm thấp nhất trên một đường đi tới một đỉnh cao hơn. Với các đỉnh có độ cao lớn nhất trên đảo, quy ước kết quả bằng \(0\): người leo núi phải ra biển để tìm một đỉnh cao hơn ở nơi khác.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương \(N,M\), lần lượt là số hàng và số cột của bản đồ. Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\) của phần này là \(E_{ij}\), độ cao của ô ở hàng \(i\), cột \(j\).

Dữ liệu ra

Dòng đầu chứa số nguyên \(P\), số đỉnh tìm được. Mỗi dòng trong \(P\) dòng tiếp theo chứa hai số nguyên: độ cao của một đỉnh và độ cao lớn nhất có thể của điểm thấp nhất trên đường tới một đỉnh cao hơn.

Liệt kê các đỉnh theo thứ tự giảm dần của độ cao. Nếu nhiều đỉnh có cùng độ cao, sắp xếp chúng theo thứ tự giảm dần của giá trị thứ hai.

Ràng buộc

• \(1 \le N,M \le 2000\) và \(N M \le 10^5\).
• \(1 \le E_{ij} \le 10^6\).

Phân nhóm

• Các bộ test có \(N \le 2\) hoặc \(M \le 2\) chiếm \(15\) điểm.
• Các bộ test có \(P \le 500\) chiếm \(50\) điểm.
• Các bộ test có \(P \le 5000\) chiếm \(80\) điểm.
• Toàn bộ các bộ test chiếm \(100\) điểm. Các mức điểm trên là tổng điểm cho những bộ test thỏa điều kiện tương ứng, không phải các phần điểm cộng thêm.

Ví dụ

6 6
21 16 9 11 6 7
21 21 10 14 15 9
18 20 8 9 13 14
11 10 9 9 8 13
8 12 12 14 13 8
7 13 12 9 5 1

4
21 0
15 11
14 13
13 12

5 3
16 14 16
14 14 15
12 17 16
12 13 10
16 11 16

5
17 0
16 15
16 14
16 13
16 13