Cross-Country Skiing Difficulty Rating

The winter Moolympics cross-country skiing course is represented by an M × N grid of elevations (1 ≤ M, N ≤ 500), where each elevation is an integer in the range 0 to 1,000,000,000. Some of the grid cells are designated as starting points.

For a starting point P, its difficulty rating is defined as the minimum possible value of D such that if a cow starts at P, she can reach at least T cells (including the starting cell) by repeatedly moving to an adjacent cell (north, south, east, or west), and for every move between two adjacent cells, the absolute difference in elevation satisfies

\( |elevation(a) - elevation(b)| \leq D \)

Your task is to compute the difficulty rating for each starting point.

inputFormat

The first line contains four integers: M, N, S and T, where S is the number of starting points (1 ≤ S ≤ M × N) and 1 ≤ T ≤ M × N.

The next M lines each contain N integers representing the elevation grid.

The following S lines each contain two integers r and c (1-indexed) specifying the row and column of a starting point.

outputFormat

For each starting point (in the input order), output a single line containing the minimum difficulty rating D such that at least T cells (including the starting point) are reachable using moves between adjacent cells with an elevation difference no more than D.

sample

3 3 2 5
1 2 3
2 3 4
3 4 5
1 1
3 3

2
2