Description

我们把一块山地划分为N x N 的小块。你已经知道了每一块地的海拔高度。

你需要回答若干个询问。

一次询问指定了一块S x S 的正方形区域（S 是一个已经给定的值），

你需要回答出在这个区域里最小海拔高度和最大海拔高度相差多少。

Input Format

第一行输入三个用空格隔开的正整数n,s,k，表示山地的大小、一次询问的大小和询问的次数。输入数据保证s<=n。

以下n 行为一个N x N 的矩阵，该矩阵描述了这个山地的高度情况。这些数字保证是不超过maxint 的正整数。

接下来k 行每行两个数x,y，询问以第x 行第y 列的格子作为左上角的S x S 的方格中最大的高度差。输入数据保证输入的x,y 有意义。

Output Format

对于每一个询问，输出询问的区域中高度差的最大值。

Sample

样例输入

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 2 6
3 5 2
2 4 6

的最大高度差是多少。

答案为6-1=5。

Hint

对于30%的数据，n<=10，k<=10；

对于50%的数据，n<=30，k<=100；

对于100%的数据，n<=100，k<=1000。