Submatrix Range Queries

You are given an N x N matrix (1 <= N <= 250). Each entry is a nonnegative integer no greater than 250. You are also given K queries (1 <= K <= 100000). All queries use the same window size B (1 <= B <= N). Each query gives the top-left position of a B x B submatrix. For every query, output the difference between the maximum and minimum entry inside that submatrix.

The first line contains three integers N, B, and K. The next N lines describe the matrix in order from row 1 to row N. Each of those lines contains N integers, listed from column 1 to column N. The next K lines each contain two integers i and j, where i is the top row of the submatrix and j is the left column of the submatrix (1 <= i, j <= N - B + 1).

Print K lines. On the lines in query order, print the difference between the maximum and minimum entry of the specified submatrix.