Northward Mountain Escape

You are given an N×M grid, where each cell has a height \(h_{i,j}\). In this grid, there are \(K\) babingbaboom creatures located at given positions. Each creature wants to run to the nearest mountain to the north. For each babingbaboom, find the nearest mountain that is to its north.

Definitions

• Mountain: A cell is considered a mountain if none of its four neighbors (up, down, left, right) has a height strictly greater than it. Formally, a cell at \((i,j)\) is a mountain if for every valid neighbor \((i',j')\), \(h_{i',j'} \le h_{i,j}\).
• North: Let the babingbaboom be at \(A(a,b)\) and a mountain be at \(B(x,y)\). Then \(B\) is considered north of \(A\) if and only if \[ \text{dis}_{A,B} = a-x \] where the Chebyshev distance is defined as \[ \text{dis}_{A,B} = \max(|a-x|,|b-y|). \] This condition is equivalent to requiring that \(x < a\) and \[ |b-y| \le a-x. \]
• Nearest: Among all mountains to the north, the "nearest" is the one that minimizes the Chebyshev distance \(a-x\). If no such mountain exists for a given babingbaboom, output \(-1\).

Input Format

The first line contains three integers \(N\), \(M\), and \(K\) — the number of rows, columns, and babingbaboom respectively.

The next \(N\) lines each contain \(M\) integers representing the grid heights \(h_{i,j}\). The grid is 1-indexed, with rows numbered from 1 to \(N\) (north to south) and columns from 1 to \(M\) (west to east).

The following \(K\) lines each contain two integers \(a\) and \(b\), the coordinates of a babingbaboom.

Output Format

For each babingbaboom, output a single line with one integer — the minimum Chebyshev distance to a mountain to its north that satisfies the above conditions, or \(-1\) if no such mountain exists.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\).

The next \(N\) lines each contain \(M\) integers, representing the grid where the \(j\)-th number in the \(i\)-th line is \(h_{i,j}\).

The following \(K\) lines each contain two integers \(a\) and \(b\) (1-indexed), representing the position of a babingbaboom.

outputFormat

Output \(K\) lines, each line containing the minimum Chebyshev distance from the corresponding babingbaboom to a mountain found to its north. If no valid mountain exists, output \(-1\) for that babingbaboom.

sample

3 3 2
1 2 1
2 2 2
1 3 1
3 2
2 3

1
1

</p>