Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Chef has a two-dimensional matrix A of dimensions N × M, (N rows and M columns).

He calls the matrix A beautiful if there exist an a×b submatrix, such that all of its elements are equal. In one minute Chef can increase one element of the matrix A by 1. Now he asks you to find out minimum time he will need to make the matrix A beautiful?

Please note that sub-matrix of a matrix is a continuous rectangular block of the matrix. It can be denoted by two pair of indices (x_{1}, y_{1}) and (x_{2}, y_{2}) where x_{1} ≤ x_{2}, y_{1} ≤ y_{2}. The content of the submatrix will be all the cells (i, j) such that x_{1} ≤ i ≤ x_{2} and y_{1} ≤ j ≤ y_{2}.

------ Input ------

There is a single test case.
The first line contains two space-separated integers N, M denoting the number of rows and columns in the matrix A, respectively
Each of the next N lines, contains M space-separated integers denoting the i-th row of the array
Next line contains one integer Q - amount of questions
Each of next Q lines contains two space-separated integers a and b denoting sizes of submatrix sought.
All questions are independent and do not influence each other. It means when you answer question, you don't need to change the array

------ Output ------

For each question, output a single line containing the minimum time that Chef needs to make an matrix A beautiful (for parameters a and b from question)

------ Constraints ------

$1 ≤ Q ≤ 50$
$1 ≤ N, M, A_{i, j} ≤ 1000$
$1 ≤ a ≤ N$
$1 ≤ b ≤ M$

------ Subtasks ------

Subtask #1 (13 pts)

$1 ≤ N, M ≤ 50$
$TL = 1s$

Subtask #2 (35 pts)

$1 ≤ N, M ≤ 200$
$TL = 2s$

Subtask #3 (52 pts)

$Original constraints$
$TL = 4s$

----- Sample Input 1 ------
3 4

1 8 3 4

5 2 3 1

3 6 2 2

4

1 1

2 2

2 3

3 2
----- Sample Output 1 ------
0

4

15

9
----- explanation 1 ------
Question #1:
Chef can choose any 1 × 1 submatrix and it will take his 0 minutes to make it beautiful.

Question #2:
The best variant is submatrix

3 1
2 2

Question #3:
The next submatrix Chef can make equal in 15 minutes

5 2 3
3 6 2

Question #4:

3 4
3 1
2 2

见题面

见题面