봉우리

산이 많은 어느 섬에 사는 한 등산가가 어떤 봉우리에 올랐고, 이제 더 높은 봉우리에 오르려고 한다.

좀 더 정확히 말하면, 섬의 모든 지점은 해수면보다 높은 양의 고도를 가진다(바다의 고도는 0이다). 등산가가 현재 서 있는 봉우리의 고도가 $E_i$라면, 그의 목표는 고도가 $E_j > E_i$인 어떤 봉우리에 도달하는 것이다. 이미 봉우리에 서 있으므로 곧바로 위로 올라가는 길은 없다. 더 높은 지점으로 가려면 먼저 더 낮은 곳으로 내려간 다음 다시 올라가야 한다. 내려가는 길은 올라가는 길만큼 값지지 않으므로, 등산가는 현재 위치에서 더 높은 봉우리로 가는 경로에서 가장 낮은 지점의 고도를 최대한 높게 만들고 싶어 한다.

예를 들어 섬의 단면이 그림과 같고 등산가가 고도 $E_4$인 봉우리에 서 있다고 하자. 더 높은 봉우리는 세 개($E_5$, $E_6$, $E_7$)이지만, 가장 낮은 지점의 고도가 가장 높은 경로는 고도 $E_7$인 봉우리로 가는 경로이다. 이 경로에서는 결코 $E_2$ 아래로 내려가지 않는다(다른 경로들에서는 $E_1$까지 내려가야 한다). 만약 $E_5$에서 출발했다면 대응하는 가장 낮은 고도는 $E_3$($E_6$으로 가는 경로)이고, $E_6$에서 출발했다면 $E_1$이 된다.

섬의 지도는 $N \times M$개의 칸으로 이루어진 2차원 직사각형 표이며, 각 칸의 수는 섬에서 그 칸에 해당하는 지역의 고도를 나타낸다. 두 칸이 적어도 한 점을 공유하면 두 칸은 인접한 것으로 본다. 따라서 (경계에 있지 않은) 모든 칸은 여덟 개의 칸과 인접한다. 경로는 연속한 두 칸이 항상 서로 인접하는 칸들의 수열이다. 평지는 고도가 같은 한 개 이상의 칸들의 집합으로, 그 집합에 속한 칸들만 지나는 경로로 임의의 두 칸이 서로 이어지는 것을 말한다. 고도가 같고 인접한 두 칸은 항상 같은 평지에 속한다. 봉우리는 어떤 칸도 자신보다 고도가 높은 인접 칸을 갖지 않는 평지이다.

섬의 모든 봉우리를 찾고, 각 봉우리에 대해 그보다 고도가 높은 어떤 봉우리로 가는 경로에서 가장 낮은 지점이 가질 수 있는 가장 높은 고도를 구하는 프로그램을 작성하라. 섬에서 가장 높은 봉우리(자신보다 높은 봉우리가 없는 봉우리)의 경우, 등산가는 더 높은 봉우리를 찾아 섬을 떠난다고 가정하므로 그 가장 낮은 지점은 $0$(해수면)이다.

첫 줄에는 두 양의 정수 $N$과 $M$($1 \le N, M \le 2000$, $N \times M \le 10^5$)이 주어진다. 각각 지도의 세로 크기와 가로 크기이다. 이어지는 $N$개의 줄에는 각각 $M$개의 정수 $E_{ij}$($1 \le E_{ij} \le 10^6$)가 공백 하나로 구분되어 주어진다. $(i+1)$번째 줄의 $j$번째 수인 $E_{ij}$는 $i$행 $j$열 칸의 고도이다.

첫 줄에 봉우리의 개수 $P$를 정수 하나로 출력한다. 이어지는 $P$개의 줄에는 각각 두 정수를 출력한다. 한 봉우리의 고도와, 그 봉우리에서 더 높은 어떤 봉우리로 가는 경로에서 가장 낮은 지점이 가질 수 있는 가장 높은 고도이다. 봉우리는 고도가 큰 순서대로 출력하며, 고도가 같은 봉우리들은 가장 낮은 지점의 고도가 큰 순서대로 출력한다.

모든 봉우리는 원으로 표시되어 있다. 고도 $15$인 봉우리에서 출발하는 가능한 경로 하나가 진한 색으로 표시되어 있다.