题目描述

FJ 正在寻找最平坦的土地种植玉米。他花了很大代价调查他的 $N \times N$ 公顷的方形农场，得到了每公顷的高度为整数 $e_i(1\le i \le N)$。

FJ 打算在农场的边长为 $B$ 的正方形小区域里种玉米，所以给了你 $K$ 组查询，每组查询包含该正方形左上角的行号、列号，他希望你求出该 $B \times B$ 正方形中最大高度和最小高度的差值。

输入格式

第一行包含三个整数 $N, B, K$。

第 $2 \sim N+1$ 行，每行都包含 $N$ 个整数，代表 $N \times N$ 公顷土地每公顷的高度 $e_i$。每行的第 1 个整数都表示第一列，第 2 个整数都表示第二列，依此类推。

接下来 $K$ 行，每行都包含两个整数（均在范围 $1 \dots N-B+1$ 内），分别表示所查询子矩阵左上角的行号和列号。

输出格式

对每个查询，都单行输出查询子矩阵中最大高度和最小高度的差值。

输入输出样例

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

5

数据范围

• $1 \le N \le 250$
• $0 \le e_i \le 250$
• $1 \le K \le 10^5$
• $1 \le B \le N$

题目来源

[USACO 2003 March Green] Cornfildes