Baltic Olympiad in Informatics: 2012 Day 1, Problem 3

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

To be more precise, every point on the island has a positive elevation above sea level (the elevation of the sea is ~0~) and if the peak the alpinist is currently on has elevation ~E_i~, then his aim is to reach some peak with elevation ~E_j~ ~(E_j>E_i)~. Because he is on a peak there is no immediate path uphill – to get to a higher point the alpinist first needs to go downhill to some lower level and only then he can go uphill again. The way down is never as remarkable as the way up, thus, the alpinist wants to maximize the elevation of the lowest point on the path from the current location to the higher peak.

For example, if the profile of the island is as shown in the figure and the alpinist is at the peak with elevation ~E_4~, then there are three peaks with higher elevation (~E_5~, ~E_6~ and ~E_7~), but the path with the lowest point having the highest elevation is the path to the peak with elevation ~E_7~ – on this path he never goes below level ~E_2~ (in the other cases he will be forced to go down to level ~E_1~). If he started from ~E_5~, the corresponding lowest level would be ~E_3~ (path to ~E_6~), but if he started from ~E_6~ it would be ~E_1~.

The map of the island is a two-dimensional rectangular table containing ~N \times M~ squares and it describes the elevation of particular parts of the island – the number in a cell describes the elevation of the corresponding region of the island. Two cells are adjacent if they share a common point. Thus, each cell (except those on the border) is adjacent to eight other. A path is a sequence of cells where each two consecutive cells are adjacent. A flat area is a set of one or more cells having the same elevation, any pair of them being connected by a path only visiting cells within the set. Any two adjacent cells with equal elevation belong to the same flat area. A peak is a flat area whose cells don't have any adjacent cells with higher elevation.

Write a program which finds all peaks on the island and for each of them finds the elevation of the highest possible lowest point on a path to some peak with a higher elevation. For the highest peak on the island (for which there is no higher peak on this island) we assume that the alpinist will leave the island looking for higher peaks, thus, the lowest point will be ~0~ (the level of the sea).

Constraints

~1 \le N, M \le 2\,000~

~N \times M \le 10^5~

~1 \le E_{ij} \le 10^6~

Subtask 1 [15%]

~N \le 2~ or ~M \le 2~

Subtask 2 [35%]

~P \le 500~

Subtask 3 [30%]

~P \le 5\,000~

Subtask 4 [20%]

No additional constraints.

Input Specification

The first line of input contains two space-separated integers ~N~ and ~M~, the height and the width of the map, respectively.

The next ~N~ lines contain the description of the map of the island. Each of these lines contains ~M~ integers ~E_{ij}~ separated by spaces. The elevation of the cell ~E_{ij}~ (corresponding to ~i^\text{th}~ row and ~j^\text{th}~ column on the map) is given as the ~j^\text{th}~ number in the ~i+1^\text{st}~ line of the file.

Output Specification

The first line of output must contain one integer ~P~, the number of peaks found on the island.

The next ~P~ lines must each contain two space-separated integers: the elevation of the particular peak and the elevation of the highest possible lowest point on the path to some higher peak. The information about peaks should be written in descending order of their elevation; if several peaks have the same elevation then they should be sorted in descending order of the lowest point elevation.

Sample Input 1

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

Sample Output 1

4
21 0
15 11
14 13
13 12

Explanation for Sample 1

All peaks are marked by circles. One of the possible paths from peak with elevation ~15~ is shown with dark colouring.

Sample Input 2

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

Sample Output 2

5
17 0
16 15
16 14
16 13
16 13