Cross-Country Skiing Difficulty Rating

The cross-country skiing course at the winter Moolympics is represented by an \(M\times N\) grid of elevations, where \(1 \le M,N \le 500\) and each elevation is an integer in the range \(0\) to \(10^9\). Some cells in the grid are marked as waypoints for the course.

The organizers want to assign a difficulty rating \(D\) to the course such that a cow can travel from any waypoint to any other waypoint by moving repeatedly from one cell to an adjacent cell (north, south, east, or west) with an absolute elevation difference of at most \(D\). The difficulty rating for the course is defined as the minimum possible \(D\) that allows all waypoints to be mutually reachable.

Formally, let the grid be defined as a matrix \(A\) of size \(M\times N\). Two cells \((i,j)\) and \((k,l)\) are adjacent if \(|i-k|+|j-l|=1\). We require that for any two waypoints \(w_1\) and \(w_2\), there exists a sequence of adjacent cells connecting \(w_1\) and \(w_2\) such that for each consecutive pair of cells \((i,j)\) and \((k,l)\) in the sequence, \(|A[i][j]-A[k][l]|\le D\). The goal is to determine the minimum \(D\) for which this condition is met.

inputFormat

The first line contains two integers \(M\) and \(N\) representing the dimensions of the grid.

The next \(M\) lines each contain \(N\) integers which represent the elevations of the grid cells in row-major order.

The following line contains an integer \(K\) representing the number of waypoints.

The next \(K\) lines each contain two integers \(r\) and \(c\) (1-indexed) denoting the row and column indices of a waypoint.

outputFormat

Output a single integer which is the minimum difficulty rating \(D\) such that any waypoint can reach any other waypoint using moves with an absolute elevation difference at most \(D\).

sample

3 3
1 2 3
4 5 6
7 8 9
2
1 1
3 3

3