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

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Data structures

Range queries


Solutions:
import sys
import numpy as np

def log2(x):
	ret = 0
	while x > 0:
		ret += 1
		x >>= 1
	return ret - 1

def get_rmq(A):
	(x, y) = A.shape
	(lx, ly) = (log2(x) + 1, log2(y) + 1)
	ret = [[np.ones(A.shape, dtype=np.int32) for i in range(ly)] for j in range(lx)]
	ret[0][0][:] = A
	for j in range(1, ly):
		j2 = 1 << j - 1
		A0 = ret[0][j - 1]
		A1 = ret[0][j]
		A1[:] = A0
		A1[:, :-j2] = np.maximum(A1[:, j2:], A1[:, :-j2])
	for i in range(1, lx):
		i2 = 1 << i - 1
		A0 = ret[i - 1][0]
		A1 = ret[i][0]
		A1[:] = A0
		A1[:-i2, :] = np.maximum(A1[i2:, :], A1[:-i2, :])
		for j in range(1, ly):
			j2 = 1 << j - 1
			A0 = ret[i][j - 1]
			A1 = ret[i][j]
			A1[:] = A0
			A1[:, :-j2] = np.maximum(A1[:, j2:], A1[:, :-j2])
	return ret

def get_max(R, x0, x1, y0, y1):
	dx = x1 - x0
	dy = y1 - y0
	lx = log2(dx)
	ly = log2(dy)
	Q = R[lx][ly]
	x1 = x1 - 2 ** lx
	y1 = y1 - 2 ** ly
	return max(Q[x0, y0], Q[x0, y1], Q[x1, y0], Q[x1, y1])

def get_cums(A):
	(m, n) = A.shape
	A0 = np.zeros((m + 1, n + 1), dtype=np.int64)
	A0[1:, 1:] = A
	return np.cumsum(np.cumsum(A0, 0), 1)

def get_sum(C, x0, x1, y0, y1):
	return C[x1, y1] - C[x0, y1] - C[x1, y0] + C[x0, y0]

def solve(R, C, x, y, a, b):
	ret = 10 ** 10
	for i in range(x - a + 1):
		for j in range(y - b + 1):
			m = get_max(R, i, i + a, j, j + b)
			s = get_sum(C, i, i + a, j, j + b)
			z = m * a * b - s
			if z < ret:
				ret = z
	return ret

def solve2(R, C, x, y, a, b):
	C00 = C[:-a, :-b]
	C01 = C[a:, :-b]
	C10 = C[:-a, b:]
	C11 = C[a:, b:]
	CC = C00 - C01 - C10 + C11
	lx = log2(a)
	ly = log2(b)
	Q = R[lx][ly]
	ab = a * b
	a0 = a - 2 ** lx
	b0 = b - 2 ** ly
	Q0 = Q[:x - a0, :y - b0]
	Q0 = np.maximum(Q0, Q[a0:, :y - b0])
	Q0 = np.maximum(Q0, Q[a0:, b0:])
	Q0 = np.maximum(Q0, Q[:x - a0, b0:])
	Q0 = Q0[:1 + x - a, :1 + y - b]
	Z = Q0 * ab - CC
	return np.min(Z)
F = sys.stdin

def readints():
	return map(int, F.readline().split())
(n, m) = readints()
A = np.zeros((n, m), dtype=np.int64)
for i in range(n):
	A[i:] = list(readints())
R = get_rmq(A)
C = get_cums(A)
(k,) = readints()
for i in range(k):
	(a, b) = readints()
	print(solve2(R, C, n, m, a, b))