Peaks

An alpinist who lives on a mountainous island has climbed to some peak and now wants to reach a higher one.

More precisely, every point on the island has a positive elevation above sea level (the sea has elevation $0$). If the peak the alpinist currently stands on has elevation $E_i$, his goal is to reach some peak with elevation $E_j > E_i$. Because he is already on a peak, there is no path leading immediately uphill: to reach a higher point he must first descend to some lower level and only then climb up again. The descent is never as rewarding as the climb, so the alpinist wants to maximize the elevation of the lowest point on the path from his current location to the higher peak.

For example, suppose the profile of the island is as shown in the figure and the alpinist stands on the peak with elevation $E_4$. There are three higher peaks ($E_5$, $E_6$, and $E_7$), but the path whose lowest point is as high as possible is the path to the peak with elevation $E_7$ — along this path he never descends below level $E_2$ (on the other paths he is forced down to level $E_1$). Had he started from $E_5$, the corresponding lowest level would be $E_3$ (the path to $E_6$); had he started from $E_6$, it would be $E_1$.

The map of the island is a two-dimensional rectangular table of $N \times M$ squares describing the elevation of the individual regions of the island: the number in a cell gives the elevation of the corresponding region. Two cells are adjacent if they share at least one common point, so every cell (except those on the border) is adjacent to eight others. A path is a sequence of cells in which every two consecutive cells are adjacent. A flat area is a set of one or more cells of equal elevation such that any two of them are connected by a path visiting only cells of the set; any two adjacent cells of equal elevation belong to the same flat area. A peak is a flat area none of whose cells has an adjacent cell of higher elevation.

Write a program that finds every peak on the island and, for each of them, the highest possible elevation of the lowest point on a path to some peak of higher elevation. For the highest peak on the island (the one that has no higher peak) we assume the alpinist leaves the island in search of higher peaks, so its lowest point is $0$ (sea level).

The first line contains two positive integers $N$ and $M$ ($1 \le N, M \le 2000$, $N \times M \le 10^5$) — the height and the width of the map. Each of the next $N$ lines contains $M$ integers $E_{ij}$ ($1 \le E_{ij} \le 10^6$) separated by single spaces. The value $E_{ij}$, given as the $j$-th number on the $(i+1)$-th line, is the elevation of the cell in row $i$ and column $j$.

On the first line print one integer $P$ — the number of peaks on the island. Each of the next $P$ lines must contain two integers: the elevation of a peak and the highest possible elevation of the lowest point on a path from that peak to some higher peak. Print the peaks in descending order of their elevation; peaks of equal elevation must be printed in descending order of the elevation of their lowest point.

All peaks are marked with circles. One possible path starting from the peak with elevation $15$ is shown in a darker shade.