Chef and Rectangle Array CHSQARR

All submissions for this problem are available.<h3> Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.</h3>

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₁, y₁) and (x₂, y₂) where x₁ ≤ x₂, y₁ ≤ y₂. The content of the submatrix will be all the cells (i, j) such that x₁ ≤ i ≤ x₂ and y₁ ≤ j ≤ y₂.

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

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

Example

Input:
3 4
1 8 3 4
5 2 3 1
3 6 2 2
4
1 1
2 2
2 3
3 2

Output:
0
4
15
9

Explanation

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