No submission language available for this problem.

Background

Special for beginners, ^_^

Description

约翰正在寻找最平坦的土地种植玉米。他花了很大的代价调查他的 N*N 公顷的方形农场（1<=N<=250）。每公顷都有一个整数高度（0<=高度<=250）。有 K （1<=K<=100000）组查询，整数 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

Limitation

1s, 1024KiB for each test case.