P7250 [BalticOI 2012] Peaks (Day 1)

There is an island of size $N \times M$, where each cell has a different elevation. Two cells are defined to be adjacent if the differences of their row and column coordinates are both at most $1$. A path is defined as a sequence of points such that every two consecutive points are adjacent. A flat region is the maximal connected set of points with the same elevation. A peak is a flat region that is not adjacent to any point with a higher elevation. Given the elevation of every point on the island, you need to find, among all peaks on the island, the maximum value of: the highest possible elevation of the lowest point that must be passed when traveling from that peak to a higher peak.

The first line contains two integers $N, M$, representing the height and width of the map. The next $N$ lines each contain $M$ integers $E_{i,j}$, describing the elevation of $(i,j)$.

The first line contains an integer $P$, representing the number of peaks on the island. The next $P$ lines each contain two integers $h_0, h_1$, representing the elevation of a peak, and the maximum possible elevation of the lowest point that must be passed when starting from this peak to reach a higher peak. The output should be sorted in descending order by $h_0$ as the primary key and $h_1$ as the secondary key. In particular, for the highest peak, $h_1 = 0$.

**Sample Explanation.**  As shown in the figure above, the circled ones are peaks. A path from the peak with elevation $15$ to another peak is highlighted in dark color. **Constraints.** - For $15\%$ of the testdata, $\min (N, M) \leq 2$. - For $50\%$ of the testdata, $P \leq 500$. - For $80\%$ of the testdata, $P \leq 5000$. - For $100\%$ of the testdata, $1 \leq N, M \leq 2000$, $N \times M \leq 10^5$, $1 \leq E_{i,j} \leq 10^6$. **Notes.** Translated from [BalticOI 2012 Day 1 T3. Peaks](http://www.boi2012.lv/data/day1/eng/peaks.pdf). Translated by ChatGPT 5