Submatrix Range Queries

Time limit2sMemory limit128 MB

Summary
Given an N x N matrix and K fixed-size BxB submatrix queries, output the max minus min value for each queried window efficiently.
Level

Medium6 of 10

Topics
Sliding window, Matrix, Array
Solved
No attempts yet

Problem

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.

Input

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).

Output

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

Examples1

  1. Example 1

    Input
    5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
    Expected output
    5