Description

约翰正在寻找最平坦的土地种植玉米。 他花了很大的代价调查他的$N ×N$ 公顷的方形农场$（1≤N ≤250）$。每 公顷都有一个整数高度（$0$$≤$高度$≤$$250$）。有$K （1≤K ≤100,000）$组 查询，整数$B （1≤B ≤N ）$是方形田地的一个边长，查询$B ×B$ 子矩 阵中最大高度和最小高度的差值。

Format

Input

第$1$行包含$3$个整数$N 、B$和$K$ 。第$2..N +1$行，每行都包 含$N$ 个整数，代表$N ×N$ 公顷每公顷的高度，每行的第$1$个整数都表示 第$1$列，第$2$个整数都表示第$2$列。接下来$K$行，每行都包含两个整数（在 $1..N -B +1$范围内），分别表示查询子矩阵左上角的行和列。

Output

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

Samples

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

来源

POJ2019