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

Deep wants to become a 7-star coder on CodeChef. To achieve this goal, everyday, he has to solve as many problems as he can. But for the first time since he was new to programming, he wasn't able to solve a single problem and lost his confidence. Can you help him solve the problem so that he gets a new boost to go ahead?

In this problem, you are given a matrix that extends infinitely to the right and down, filled with values as shown below.

Let $(x, y)$ denote the cell in the $x$-th row and $y$-th column. The upper-left cell $(1, 1)$ contains an integer $1$. You begin at the cell $(x_{1}, y_{1})$ and must walk to the cell $(x_{2}, y_{2})$ by only moving right and down. Formally, from the cell $(x, y)$, in one step you can move to the cell $(x+1, y)$ or $(x, y+1)$.

The value of a path is the sum of the values in all visited cells, including $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$. You need to calculate the maximum possible value on the path of a path from $(x_{1}, y_{1})$ to $(x_{2}, y_{2})$.

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

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains of a single line of input, four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$.

------ Output ------
For each test case, output in a single line the maximum possible value of a path from $(x_{1}, y_{1})$ to $(x_{2}, y_{2})$.

------ Constraints  ------
$1 ≤ T ≤ 1000$
$1≤ x_{1}≤ x_{2}≤ 1000$
$1≤ y_{1}≤ y_{2}≤ 1000$

----- Sample Input 1 ------ 
1
1 1 3 3
----- Sample Output 1 ------ 
32
----- explanation 1 ------ 
The only way to achieve the maximum possible value is by visiting cells with values $1 \to 3 \to 6 \to 9 \to 13$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Range queries

Constructive algorithms


Solutions:
t = int(input())
n = 1001
l = [[0 for i in range(n)] for i in range(n)]
for i in range(1, n):
	l[i][1] = i * (i + 1) // 2
for j in range(1, n):
	for k in range(2, n):
		l[j][k] = l[j][k - 1] + (k - 1) + (j - 1)
for z in range(t):
	(r1, c1, r2, c2) = list(map(int, input().split()))
	s = 0
	for a in range(r1, r2 + 1):
		s += l[a][c1]
	for b in range(c1 + 1, c2 + 1):
		s += l[r2][b]
	print(s)


T = int(input())
N = 1001
inf = [[0 for _ in range(N)] for _ in range(N)]
for i in range(1, N):
	inf[i][1] = i * (i + 1) // 2
for i in range(1, N):
	for j in range(2, N):
		inf[i][j] = inf[i][j - 1] + (j - 1) + (i - 1)
for _ in range(T):
	(r1, c1, r2, c2) = list(map(int, input().split()))
	Sum = 0
	for i in range(r1, r2 + 1):
		Sum += inf[i][c1]
	for i in range(c1 + 1, c2 + 1):
		Sum += inf[r2][i]
	print(Sum)


from sys import stdin, stdout
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	(x1, y1, x2, y2) = list(map(int, input().strip().split()))
	point1 = (1, y1)
	point2 = (x1, y1)
	point2 = (x2, y1)
	point1_value = 1 + (y1 - 1) * y1 // 2
	diff1 = 1 + y1
	diff2 = x1 + y1
	diff3 = x2 + y1 - 1
	point2_value = point1_value + (x1 - 1) * (2 * diff1 + x1 - 2) // 2
	point3_value = point1_value + (x2 - 1) * (2 * diff1 + x2 - 2) // 2
	ans = 0
	for i in range(x2 - x1 + 1):
		ans += point2_value + i * (2 * diff2 + i - 1) // 2
	for i in range(y2 - y1 + 1):
		ans += point3_value + i * (2 * diff3 + i - 1) // 2
	ans = ans - point3_value
	print(ans)


from itertools import accumulate

def val_at(x, y, trs):
	return trs[y + x - 2] + x
tri = list(accumulate(range(2 * 1000 + 1)))
actri = [0] + list(accumulate(tri))
T = int(input())
for tx in range(T):
	(x1, y1, x2, y2) = map(int, input().split())
	if x2 < x1:
		(x1, y1, x2, y2) = (x2, y2, x1, y1)
	res = tri[x2 - 1] - tri[x1 - 1] + actri[y1 + x2 - 2] - actri[y1 + x1 - 2]
	if y2 < y1:
		(y1, y2) = (y2, y1)
	res += x2 * (y2 + 1 - y1) + actri[y2 + 1 + x2 - 2] - actri[y1 + x2 - 2]
	print(res)


matrix = [[0 for i in range(1000)] for i in range(1000)]
matrix[0][0] = 1
for i in range(1, 1000):
	matrix[i][0] += matrix[i - 1][0] + i + 1
for i in range(0, 1000):
	for j in range(1, 1000):
		matrix[i][j] = matrix[i][j - 1] + j + i
t = int(input())
for _ in range(t):
	x1x2y1y2 = list(map(int, input().split()))
	x1 = x1x2y1y2[0]
	y1 = x1x2y1y2[1]
	x2 = x1x2y1y2[2]
	y2 = x1x2y1y2[3]
	sum1 = 0
	for i in range(x1 - 1, x2):
		sum1 += matrix[i][y1 - 1]
	for j in range(y1, y2):
		sum1 += matrix[x2 - 1][j]
	print(sum1)


from sys import stdin
for _ in range(int(stdin.readline())):
	(x1, y1, x2, y2) = map(int, stdin.readline().split())
	d2 = x1 + y1
	t2 = y1 + 1
	d1 = x2 + y1 - 1
	q = 0
	v = y1 * y1 / 2 - y1 / 2 + 1
	for i in range(1, x1):
		v += t2
		t2 += 1
	for i in range(x1, x2):
		q += v
		v += d2
		d2 += 1
	for i in range(y1, y2 + 1):
		q += v
		v += d1
		d1 += 1
	print(int(q))


def maximum(r1, c1, r2, c2, inf):
	Sum = 0
	for i in range(r1, r2 + 1):
		Sum += inf[i][c1]
	for j in range(c1 + 1, c2 + 1):
		Sum += inf[r2][j]
	return Sum
inf = [[0 for i in range(1001)] for i in range(1001)]
for i in range(1, 1001):
	inf[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		inf[i][j] = inf[i][j - 1] + (i - 1) + (j - 1)
for _ in range(int(input())):
	(r1, c1, r2, c2) = list(map(int, input().split()))
	print(maximum(r1, c1, r2, c2, inf))


for i in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	lvl = x1 + y1 - 2
	ans = lvl * (lvl + 1) // 2 + x1
	while x1 < x2:
		x1 += 1
		lvl = x1 + y1 - 2
		ans += lvl * (lvl + 1) // 2 + x1
	while y1 < y2:
		y1 += 1
		lvl = x1 + y1 - 2
		ans += lvl * (lvl + 1) // 2 + x1
	print(ans)


arr = [[0 for i in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	arr[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		arr[i][j] = arr[i][j - 1] + (i - 1) + (j - 1)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	sumup = arr[x1][y1]
	while x1 < x2 and y1 < y2:
		right = arr[x1][y1 + 1]
		down = arr[x1 + 1][y1]
		if right > down:
			y1 += 1
			sumup += arr[x1][y1]
		if down >= right:
			x1 += 1
			sumup += arr[x1][y1]
	if x1 == x2 and y1 != y2:
		sumup += sum(arr[x1][y1 + 1:y2 + 1])
	if y1 == y2 and x1 != x2:
		for k in range(x1 + 1, x2 + 1):
			sumup += arr[k][y1]
	print(sumup)


S = [[0 for i in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	S[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		S[i][j] = S[i][j - 1] + (i - 1) + (j - 1)
T = int(input())
for i in range(T):
	(x1, y1, x2, y2) = map(int, input().split())
	max_path = 0
	for i in range(x1, x2 + 1):
		max_path += S[i][y1]
	for i in range(y1 + 1, y2 + 1):
		max_path += S[x2][i]
	print(max_path)


a = [[0 for i in range(1000)] for j in range(1000)]
a[0][0] = 1
for i in range(1, 1000):
	a[i][0] = a[i - 1][0] + i + 1
for i in range(1000):
	for j in range(1, 1000):
		a[i][j] = a[i][j - 1] + i + j
t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for j in range(x1 - 1, x2):
		ans += a[j][y1 - 1]
	for j in range(y1, y2):
		ans += a[x2 - 1][j]
	print(ans)


t = int(input())
infiniteMat = [[0 for i in range(1001)] for i in range(1001)]
infiniteMat[1][1] = 1
for i in range(2, 1001):
	infiniteMat[i][1] = infiniteMat[i - 1][1] + i
for i in range(1, 1001):
	for j in range(2, 1001):
		infiniteMat[i][j] = infiniteMat[i][j - 1] + i + j - 2
for _ in range(t):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	ans = 0
	for i in range(x1, x2 + 1):
		ans += infiniteMat[i][y1]
	for i in range(y1 + 1, y2 + 1):
		ans += infiniteMat[x2][i]
	print(ans)


arr = [[0 for i in range(1000)] for j in range(1000)]
for i in range(1000):
	arr[i][0] = (i + 1) * (i + 2) // 2
for i in range(1000):
	for j in range(1, 1000, 1):
		arr[i][j] = arr[i][j - 1] + j + i
for i in range(int(input())):
	(r1, c1, r2, c2) = [int(x) for x in input().split()]
	r1 -= 1
	c1 -= 1
	r2 -= 1
	c2 -= 1
	sum = arr[r1][c1]
	for j in range(r1 + 1, r2 + 1, 1):
		sum += arr[j][c1]
	for j in range(c1 + 1, c2 + 1, 1):
		sum += arr[r2][j]
	print(sum)


for _ in range(int(input())):
	(x, y, x1, y1) = map(int, input().split())
	n = 0
	for i in range(x):
		n += i + 1
	for i in range(y - 1):
		n += x + i
	ans = n
	diff = x + y
	for i in range(x1 - x):
		n += diff + i
		ans += n
	diff = x1 + y - 1
	for i in range(y1 - y):
		n += diff + i
		ans += n
	print(ans)


inf = []
for i in range(1000):
	for j in range(1000):
		if j == 0:
			temp = []
			temp.append((i + 1) * (i + 2) // 2)
			inf.append(temp)
		else:
			inf[i].append(inf[i][j - 1] + i + j)
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = [int(x) - 1 for x in input().split()]
	ans = 0
	for i in range(x1, x2 + 1):
		ans += inf[i][y1]
	for j in range(y1 + 1, y2 + 1):
		ans += inf[x2][j]
	print(ans)


m = [[0 for i in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	m[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		m[i][j] = m[i][j - 1] + (i - 1) + (j - 1)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for i in range(x1, x2 + 1):
		ans += m[i][y1]
	for i in range(y1 + 1, y2 + 1):
		ans += m[x2][i]
	print(ans)


t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	p = x1 + y1
	sum = 0
	for i in range(x1, x2 + 1):
		sum += p * (p - 1) // 2 - y1 + 1
		p += 1
	p = x2 + y1 + 1
	for i in range(y1 + 1, y2 + 1):
		sum += p * (p - 1) // 2 - i + 1
		p += 1
	print(sum)


t = int(input())
for case in range(t):
	(x1, y1, x2, y2) = map(lambda x: int(x) - 1, input().split())
	pathSum = 0
	for row in range(x1, x2 + 1):
		x = row + y1 + 1
		cur = x * (x - 1) // 2 + row + 1
		pathSum += cur
	for col in range(y1 + 1, y2 + 1):
		x = x2 + col + 1
		cur = x * (x - 1) // 2 + x2 + 1
		pathSum += cur
	print(pathSum)


m = []
for i in range(1000):
	n = []
	for j in range(1000):
		n.append(0)
	m.append(n)
m[0][0] = 1
t = 1
for i in range(1, 1000):
	m[0][i] = m[0][i - 1] + t
	t += 1
t = 2
for i in range(1, 1000):
	m[i][0] = m[i - 1][0] + t
	t += 1
for i in range(1, 1000):
	t = i + 1
	for j in range(1, 1000):
		m[i][j] = m[i][j - 1] + t
		t += 1
test = int(input())
while test:
	(x1, y1, x2, y2) = input().split()
	x1 = int(x1) - 1
	x2 = int(x2) - 1
	y1 = int(y1) - 1
	y2 = int(y2) - 1
	s = m[x1][y1]
	while x1 != x2:
		x1 += 1
		s += m[x1][y1]
	while y1 != y2:
		y1 += 1
		s += m[x1][y1]
	print(s)
	test -= 1


(i1, j1) = (1001, 1001)
inf = [[0 for x in range(i1)] for y in range(j1)]
for i in range(1, 1000 + 1):
	inf[i][1] = i * (i + 1) / 2
	for j in range(2, 1000 + 1):
		inf[i][j] = inf[i][j - 1] + (j - 1) + (i - 1)
t = int(input())
for z in range(t):
	sum = 0
	(x1, y1, x2, y2) = tuple(map(int, input().split()))
	i = x1
	while i <= x2:
		sum = sum + inf[i][y1]
		i += 1
	i = y1 + 1
	while i <= y2:
		sum = sum + inf[x2][i]
		i += 1
	print(int(sum))


mx = 1003
mat = [[0 for i in range(mx)] for j in range(mx)]
pre_r = [[0 for i in range(mx)] for j in range(mx)]
pre_c = [[0 for i in range(mx)] for j in range(mx)]
inc_col = 1
inc_row = 0
curr_col = 0
curr_row = 1
for i in range(1, mx):
	inc_row = inc_col
	curr_col += inc_col
	curr_row = curr_col
	inc_col += 1
	for j in range(1, mx):
		mat[i][j] = curr_row
		pre_r[i][j] = pre_r[i][j - 1] + mat[i][j]
		pre_c[i][j] = pre_c[i - 1][j] + mat[i][j]
		curr_row += inc_row
		inc_row += 1
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().strip().split())
	if x1 == x2 and y1 == y2:
		print(0)
	else:
		val1 = pre_c[x2][y1] - pre_c[x1][y1] + mat[x1][y1]
		val2 = pre_r[x2][y2] - pre_r[x2][y1]
		val = val2 + val1
		print(val)


mat = [[[] for i in range(1005)] for j in range(1005)]
for i in range(1, 1001):
	mat[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		mat[i][j] = mat[i][j - 1] + (j - 1) + (i - 1)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	s = 0
	for i in range(x1, x2 + 1):
		s += mat[i][y1]
	for j in range(y1 + 1, y2 + 1):
		s += mat[x2][j]
	print(s)


matrix = [[0 for i in range(2000)] for j in range(2000)]
for i in range(1, 2000):
	matrix[i][1] = i * (i + 1) // 2
	for j in range(2, 2000):
		matrix[i][j] = matrix[i][j - 1] + (j - 1) + (i - 1)
for _ in range(int(input())):
	s = 0
	(x1, y1, x2, y2) = map(int, input().split())
	for i in range(x1, x2 + 1):
		s += matrix[i][y1]
	for j in range(y1 + 1, y2 + 1):
		s += matrix[x2][j]
	print(s)


t = int(input())
for k in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	a = 0
	for i in range(x1):
		a += i + 1
	for j in range(y1 - 1):
		a += x1 + j
	a1 = a
	b1 = x1 + y1
	for i in range(x2 - x1):
		a += b1 + i
		a1 += a
	b1 = x2 + y1 - 1
	for i in range(y2 - y1):
		a += b1 + i
		a1 += a
	print(a1)


T = int(input())
lst = [[0 for i in range(1000)] for j in range(1000)]
lst[0][0] = 1
m = 2
for i in range(1, 1000):
	lst[i][0] = lst[i - 1][0] + m
	m += 1
for i in range(1000):
	k = i + 1
	for j in range(1, 1000):
		lst[i][j] = lst[i][j - 1] + k
		k += 1
while T > 0:
	T = T - 1
	(x1, y1, x2, y2) = map(int, input().split())
	sum = 0
	for i in range(x1 - 1, x2):
		sum += lst[i][y1 - 1]
	for i in range(y1, y2):
		sum += lst[x2 - 1][i]
	print(sum)


matrix = [[0 for _ in range(1001)] for _ in range(1001)]
for i in range(1, 1001):
	matrix[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		matrix[i][j] = matrix[i][j - 1] + (i - 1) + (j - 1)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	sum_ = 0
	for i in range(x1, x2 + 1):
		sum_ += matrix[i][y1]
	for i in range(y1 + 1, y2 + 1):
		sum_ += matrix[x2][i]
	print(sum_)


l = [[0] * 1000 for i in range(1000)]
for i in range(0, 1000):
	l[i][0] = (i + 1) * (i + 2) // 2
	for j in range(1, 1000):
		l[i][j] = l[i][j - 1] + j + i
for t in range(int(input())):
	(r1, c1, r2, c2) = map(int, input().split())
	ans = 0
	for i in range(r1 - 1, r2 - 1):
		ans += l[i][c1 - 1]
	for j in range(c1 - 1, c2):
		ans += l[r2 - 1][j]
	print(ans)


matrix = [[None for y in range(1005)] for x in range(1005)]

def genInfMat():
	for i in range(1, 1001):
		matrix[i][1] = i * (i + 1) // 2
		for j in range(2, 1001):
			matrix[i][j] = matrix[i][j - 1] + (j - 1) + (i - 1)
genInfMat()
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	score = 0
	while x1 <= x2:
		score += matrix[x1][y1]
		x1 += 1
	while y1 < y2:
		y1 += 1
		score += matrix[x2][y1]
	print(score)


t = int(input())
arr = []
mk = 2 * 1000
for i in range(mk + 1):
	arr.append([0] * (mk + 1))
n = 1
for k in range(2, 2 * mk + 1):
	i = 1
	while k - i > mk:
		i += 1
	while i < k and i < mk + 1:
		arr[i][k - i] = n
		i += 1
		n += 1
for l in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for i in range(x1, x2 + 1):
		ans += arr[i][y1]
	for i in range(y1 + 1, y2 + 1):
		ans += arr[x2][i]
	print(ans)


def matCalc():
	m = []
	r = []
	c = []
	n = 1
	i = 0
	j = 0
	for k in range(0, 2000):
		m.append([])
		while j >= 0:
			m[i].append(n)
			j -= 1
			i += 1
			n += 1
		j = k + 1
		i = 0
	return m

def printMaxSum(x1, y1, x2, y2, m):
	val = 0
	for i in range(x1 - 1, x2):
		val += m[i][y1 - 1]
	for j in range(y1, y2):
		val += m[x2 - 1][j]
	print(val)
m = matCalc()
nt = int(input())
for i in range(0, nt):
	l = list(map(int, input().strip().split(' ')))
	x1 = l[0]
	y1 = l[1]
	x2 = l[2]
	y2 = l[3]
	printMaxSum(x1, y1, x2, y2, m)


T = int(input())
dp = [[1] * 1000 for i in range(1000)]
for i in range(1, 1000):
	dp[i][0] = dp[i - 1][0] + i + 1
for j in range(1, 1000):
	dp[0][j] = dp[0][j - 1] + j
for i in range(1, 1000):
	for j in range(1, 1000):
		dp[i][j] = dp[i][j - 1] + i + j
for i in range(T):
	a = [int(s) for s in input().split()]
	(x_1, y_1, x_2, y_2) = (a[0], a[1], a[2], a[3])
	ans = 0
	for k in range(x_1 - 1, x_2):
		ans += dp[k][y_1 - 1]
	for k in range(y_1, y_2):
		ans += dp[x_2 - 1][k]
	print(ans)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	x = 1
	for i in range(1, b):
		x = x + i
	for i in range(1, a):
		x = x + i + b
	y = x
	for i in range(a, c):
		x = x + i + b
		y += x
	for i in range(b, d):
		x = x + i + (c - 1)
		y += x
	print(y)


l = [[0 for i in range(1001)] for j in range(1001)]
for i in range(0, 1001):
	l[i][0] = (i + 1) * (i + 2) // 2
	for j in range(1, 1001):
		l[i][j] = l[i][j - 1] + j + i
t = int(input())
while t:
	(a, b, c, d) = map(int, input().split())
	s = 0
	for i in range(a - 1, c):
		s += l[i][b - 1]
	for i in range(b, d):
		s += l[c - 1][i]
	print(s)
	t -= 1


for _ in range(int(input())):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	(v, i, j) = (0, 1, 1)
	while i != x1 + 1:
		v = v + i
		i += 1
	i -= 1
	while j != y1:
		v = v + i
		i += 1
		j += 1
	s = v
	while x1 != x2:
		v = v + x1 + y1
		s = s + v
		x1 += 1
	x1 -= 1
	while y1 != y2:
		v = v + x1 + y1
		s = s + v
		y1 += 1
	print(s)


def num(x, y):
	n = (x + y - 2) * (x + y - 1)
	n = n / 2
	n = n + y
	return int(n)
t = int(input())
while t > 0:
	ans = 0
	t = t - 1
	(p, q, r, s) = input().split()
	p = int(p)
	q = int(q)
	r = int(r)
	s = int(s)
	for i in range(p, r):
		ans = ans + num(q, i)
	for j in range(q, s + 1):
		ans = ans + num(j, r)
	print(ans)


import numpy as np
a = np.zeros((1001, 1001))
for i in range(1, 1001):
	a[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		a[i][j] = a[i][j - 1] + j - 1 + i - 1
t = int(input())
for k in range(0, t):
	(x, y, x_, y_) = map(int, input().split())
	ans = 0
	while x < x_:
		ans += a[x][y]
		x += 1
	while y <= y_:
		ans += a[x_][y]
		y += 1
	print(int(ans))


def array():
	arr = [[0 for i in range(1001)] for j in range(1001)]
	for i in range(1, 1001):
		arr[i][1] = i * (i + 1) // 2
		for j in range(2, 1001):
			arr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)
	return arr
a = array()
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	sum = 0
	for i in range(x1, x2 + 1):
		sum += a[i][y1]
	for i in range(y1 + 1, y2 + 1):
		sum += a[x2][i]
	print(sum)


def val(x, y):
	if y > 1:
		return x * (x + 1) // 2 + (y - 1) * x + (y - 1) * (y - 2) // 2
	else:
		return x * (x + 1) // 2
t = int(input())
for k in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	if x1 == x2 and y1 != y2:
		for i in range(y1, y2 + 1):
			ans += val(x1, i)
	elif y1 == y2 and x1 != x2:
		for i in range(x1, x2 + 1):
			ans += val(i, y1)
	else:
		for i in range(x1, x2 + 1):
			ans += val(i, y1)
		for i in range(y1 + 1, y2 + 1):
			ans += val(x2, i)
	print(ans)


n = 1000
L = []
(c, d) = (1, 1)
for i in range(n):
	(a, b) = (c, d)
	L.append([])
	for j in range(n):
		L[i].append(a)
		a += b
		b += 1
	d += 1
	c = c + i + 2
for i in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	s = 0
	for i in range(x1 - 1, x2):
		s += L[i][y1 - 1]
	for i in range(y1, y2):
		s += L[x2 - 1][i]
	print(s)


def val(x, y):
	s = x + y
	return x + (s - 1) * (s - 2) // 2
T = int(input())
for _ in range(T):
	(a, b, p, q) = map(int, input().split())
	res = 0
	for x in range(a, p + 1):
		res += val(x, b)
	for y in range(b + 1, q + 1):
		res += val(p, y)
	print(res)


try:
	li = []
	for i in range(1, 1001):
		li.append([int(i * (i + 1) / 2)])
	for i in range(1000):
		prev = li[i][0]
		for j in range(2, 1001):
			a = prev + j - 1 + i
			li[i].append(a)
			prev = a
	for _ in range(int(input())):
		(x1, y1, x2, y2) = map(int, input().split())
		ans = 0
		for i in range(x1 - 1, x2):
			ans = ans + li[i][y1 - 1]
		for i in range(y1, y2):
			ans = ans + li[x2 - 1][i]
		print(ans)
except:
	pass


for _ in range(int(input())):
	m = list(map(int, input().split()))
	x1 = m[0]
	y1 = m[1]
	x2 = m[2]
	y2 = m[3]
	s = 1
	for i in range(1, x1):
		s = s + i + 1
	for i in range(x1, x1 + y1 - 1):
		s = s + i
	sum = s
	for i in range(x1 + y1, x2 + y1):
		s = s + i
		sum = sum + s
	for i in range(x2 + y1 - 1, x2 + y2 - 1):
		s = s + i
		sum = sum + s
	print(sum)


from copy import deepcopy
MAX = 1001
mat = [[0 for j in range(MAX + 1)] for i in range(MAX + 1)]
pre_r = deepcopy(mat)
pre_c = deepcopy(mat)

def pre_compute():
	for r in range(1, MAX + 1):
		mat[r][1] = r * (r + 1) // 2
		for c in range(2, MAX + 1):
			mat[r][c] = mat[r][c - 1] + r + c - 2
	for r in range(1, MAX + 1):
		pre_r[r][1] = mat[r][1]
		for c in range(2, MAX + 1):
			pre_r[r][c] = pre_r[r][c - 1] + mat[r][c]
	for c in range(1, MAX + 1):
		pre_c[1][c] = mat[1][c]
		for r in range(2, MAX + 1):
			pre_c[r][c] = pre_c[r - 1][c] + mat[r][c]

def solve():
	(x1, y1, x2, y2) = map(int, input().split())
	ans = pre_c[x2][y1] - pre_c[x1 - 1][y1] + pre_r[x2][y2] - pre_r[x2][y1]
	print(ans)
pre_compute()
for tc in range(int(input())):
	solve()


t = int(input())
b = []
for i in range(0, 1000):
	s = (i + 1) * (i + 2) // 2
	k = []
	k.append(s)
	for j in range(1, 1000):
		s = k[j - 1] + j + i
		k.append(s)
	b.append(k)
while t > 0:
	t = t - 1
	a = [int(x) for x in input().split()]
	s = 0
	for i in range(a[0] - 1, a[2]):
		s = s + b[i][a[1] - 1]
	for i in range(a[1], a[3]):
		s = s + b[a[2] - 1][i]
	print(s)


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	v = 1
	for i in range(1, y1):
		v += i
	for i in range(1, x1):
		v += i + y1
	u = v
	for i in range(x1, x2):
		v += i + y1
		u += v
	for i in range(y1 - 1, y2 - 1):
		v += i + x2
		u += v
	print(u)


def f(x, y):
	return (x + y) * (x + y - 1) // 2 - y + 1
n = int(input())
for j in range(n):
	(y, x, y2, x2) = map(int, input().strip().split())
	s = f(y, x)
	while x != x2 or y != y2:
		if y != y2:
			y += 1
		else:
			x += 1
		s += f(y, x)
	print(s)
	s = 0


(n, l) = (int(input()), [])
for j in range(n):
	(y, x, y2, x2) = map(int, input().strip().split())
	s = ((x + y) ** 2 - 3 * x - y) / 2 + 1
	while x != x2 or y != y2:
		if y != y2:
			y += 1
		else:
			x += 1
		s += ((x + y) ** 2 - 3 * x - y) / 2 + 1
	l.append(s)
	s = 0
for i in l:
	print(int(i))


from sys import stdin, stdout
input = stdin.readline

def im():
	return map(int, input().split())

def ii():
	return int(input())

def il():
	return list(map(int, input().split()))

def ins():
	return input()[:-1]
lis = [[0] * 1005 for _ in range(1005)]
for i in range(1, 1001):
	lis[i][1] = lis[i - 1][1] + i
	for j in range(2, 1001):
		lis[i][j] = lis[i][j - 1] + (j - 1) + (i - 1)
for _ in range(ii()):
	(x1, y1, x2, y2) = im()
	ans = 0
	while x1 < x2:
		ans += lis[x1][y1]
		x1 += 1
	while y1 < y2:
		ans += lis[x1][y1]
		y1 += 1
	ans += lis[x2][y2]
	print(ans)


import math
rows = 1000
cols = 1000
arr = [[0 for c in range(cols + 1)] for r in range(rows + 1)]
for i in range(1, 1001):
	arr[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		arr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)
for _ in range(int(input())):
	(r1, c1, r2, c2) = list(map(int, input().split()))
	sum = 0
	for i in range(r1, r2 + 1):
		sum += arr[i][c1]
	for i in range(c1 + 1, c2 + 1):
		sum += arr[r2][i]
	print(sum)


import math
rows = 1000
cols = 1000
arr = [[0 for c in range(cols + 1)] for r in range(rows + 1)]
for i in range(1, 1001):
	arr[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		arr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)
test_cases = int(input())
for test_case in range(test_cases):
	(r1, c1, r2, c2) = list(map(int, input().split()))
	col_sum = 0
	for r in range(r1, r2 + 1):
		col_sum += arr[r][c1]
	row_sum = 0
	for c in range(c1 + 1, c2 + 1):
		row_sum += arr[r2][c]
	print(col_sum + row_sum)


import math
rows = 1000
cols = 1000
arr = [[0 for c in range(cols + 1)] for r in range(rows + 1)]
num = 1
for r in range(1, rows + 1):
	diff = r - 1
	for c in range(1, cols + 1):
		if c == 1:
			arr[r][c] = arr[r - 1][c] + r
		else:
			arr[r][c] = arr[r][c - 1] + diff
		diff += 1
test_cases = int(input())
for test_case in range(test_cases):
	(r1, c1, r2, c2) = list(map(int, input().split()))
	col_sum = 0
	for r in range(r1, r2 + 1):
		col_sum += arr[r][c1]
	row_sum = 0
	for c in range(c1 + 1, c2 + 1):
		row_sum += arr[r2][c]
	print(col_sum + row_sum)


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	s = 1
	for i in range(1, x1):
		s = s + i + 1
	for i in range(x1, x1 + y1 - 1):
		s = s + i
	summ = s
	for i in range(x1 + y1, x2 + y1):
		s = s + i
		summ += s
	for i in range(x2 + y1 - 1, x2 + y2 - 1):
		s = s + i
		summ += s
	print(summ)


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().strip().split())
	y = [1]
	for i in range(y1 - 1):
		y.append(y[i] + i + 1)
	x = [y[-1]]
	for i in range(1, x2):
		x.append(x[i - 1] + y1 + i)
	bottom = sum(x[x1 - 1:x2])
	y_f = [1]
	for i in range(1, x2):
		y_f.append(y_f[i - 1] + i + 1)
	x_f = [y_f[-1]]
	for i in range(1, y2):
		x_f.append(x_f[i - 1] + x2 - 1 + i)
	right = sum(x_f[y1 - 1:y2])
	right_f = right - x[-1]
	print(right_f + bottom)


ncases = int(input())
q = []
while ncases:
	q.append(list(map(lambda x: int(x), input().split())))
	ncases -= 1
r = 1001
matrix = [[None for _ in range(r)] for i in range(r)]
matrix[0][0] = 1
cnt = 1
for i in range(1, r):
	matrix[0][i] = matrix[0][i - 1] + cnt
	cnt += 1
cnt = 2
for i in range(1, r):
	matrix[i][0] = matrix[i - 1][0] + cnt
	cnt += 1
	cnt1 = i + 2
	for j in range(1, r):
		matrix[i][j] = matrix[i - 1][j] + cnt1
		cnt1 += 1

def solver(li):
	(x1, y1, x2, y2) = li
	(x1, x2, y1, y2) = (x1 - 1, x2 - 1, y1 - 1, y2 - 1)
	s = 0
	for i in range(min(y1, y2), max(y1, y2) + 1):
		s += matrix[max(x1, x2)][i]
	for i in range(min(x1, x2), max(x1, x2)):
		s += matrix[i][min(y1, y2)]
	return s
for li in q:
	print(solver(li))


grid = [1]
fu = [i for i in range(1, 1001)]
grid += fu
final = []
final.append(grid)
d = [1] * 1000
for i in range(2, 1002):
	c = [i] + d
	final.append(c)
for i in range(1001):
	for j in range(1, 1001):
		final[i][j] += final[i][j - 1]
for i in range(1001):
	for j in range(1, 1001):
		final[j][i] += final[j - 1][i]
t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	c = 0
	for i in range(x1, x2 + 1):
		c += final[i - 1][y1 - 1]
	for i in range(y1, y2 + 1):
		c += final[x2 - 1][i - 1]
	c -= final[x2 - 1][y1 - 1]
	print(c)


def f(x, y):
	return (x + y) * (x + y - 1) // 2 - y + 1
T = int(input())
for n1 in range(T):
	(x1, y1, x2, y2) = [int(i) for i in input().split(' ')]
	s = 0
	for x in range(x1, x2):
		s += f(x, y1)
	for y in range(y1, y2 + 1):
		s += f(x2, y)
	print(s)


def value(x, y):
	return x * (x + 1) // 2 + (2 * x + y - 2) * (y - 1) // 2
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	sum = 0
	for x in range(x1, x2 + 1):
		sum += value(x, y1)
	for y in range(y1 + 1, y2 + 1):
		sum += value(x2, y)
	print(sum)


arr = []
c = 1
for i in range(1, 1001):
	arr.append(c)
	c += i
matrix = []
matrix.append(arr)
k = 2
for i in range(2, 1001):
	newarr = []
	c = k
	for j in matrix[-1]:
		newarr.append(j + c)
		c += 1
	matrix.append(newarr)
	k += 1
for t in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	ans = 0
	for i in range(x1, x2 + 1):
		ans += matrix[i - 1][y1 - 1]
	for i in range(y1 + 1, y2 + 1):
		ans += matrix[x2 - 1][i - 1]
	print(ans)


a = []
s = 1
i_s = 1
r = 2
c = 1
i_c = 1
c_c = 1
for i in range(1000):
	v = []
	for j in range(1000):
		v.append(s)
		s += c
		c += c_c
	a.append(v)
	s = i_s + r
	i_s = s
	r += 1
	c = i_c + 1
	i_c = c
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	su = sum(a[x2 - 1][y1 - 1:y2])
	for i in range(x1 - 1, x2 - 1):
		su += a[i][y1 - 1]
	print(su)


arr = [[0 for i in range(1000)] for j in range(1000)]
start = 0
for i in range(len(arr)):
	start += i + 1
	inc = i
	for j in range(len(arr)):
		if j == 0:
			arr[i][j] = start
		else:
			arr[i][j] = arr[i][j - 1] + inc
		inc += 1
for _ in range(int(input())):
	l = input().split()
	(x1, y1, x2, y2) = (int(l[0]), int(l[1]), int(l[2]), int(l[3]))
	sums = 0
	for i in range(x1, x2 + 1):
		sums += arr[i - 1][y1 - 1]
	for i in range(y1 + 1, y2 + 1):
		sums += arr[x2 - 1][i - 1]
	print(sums)


def val(r, c):
	s = c + r - 2
	return int(s * (s + 1) / 2 + r)
T = int(input())
for i in range(T):
	(r1, c1, r2, c2) = map(int, input().split())
	path = 0
	for r in range(r1, r2 + 1):
		path += val(r, c1)
	for c in range(c1 + 1, c2 + 1):
		path += val(r2, c)
	print(path)


rows = 1000
cols = 1000
inf = [[0 for c in range(cols + 1)] for r in range(rows + 1)]
for i in range(1, 1001):
	inf[i][1] = int(i * (i + 1) / 2)
	for j in range(2, 1001):
		inf[i][j] = inf[i][j - 1] + j - 1 + i - 1
for t in range(int(input())):
	sum = 0
	(x1, y1, x2, y2) = map(int, input().split())
	for i in range(x1, x2 + 1):
		sum = sum + inf[i][y1]
	for j in range(y1 + 1, y2 + 1):
		sum = sum + inf[x2][j]
	print(sum)


t = int(input())
arr = [[0 for _ in range(1001)] for _ in range(1001)]
for i in range(1, 1001):
	arr[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		arr[i][j] = arr[i][j - 1] + i + j - 2
for i in range(t):
	(r1, c1, r2, c2) = list(map(int, input().split(' ')))
	s = 0
	for i in range(r1, r2 + 1):
		s = s + arr[i][c1]
	for j in range(c1 + 1, c2 + 1):
		s = s + arr[r2][j]
	print(s)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	x1 = l[0]
	y1 = l[1]
	x2 = l[2]
	y2 = l[3]
	temp1 = x1
	temp2 = y1
	tempval = x1 * (x1 + 1) // 2
	news = (y1 - 1) * (2 * x1 + y1 - 2) // 2
	val = tempval + news
	s = val
	while temp1 < x2:
		res = val + temp1 + temp2
		s = s + res
		temp1 = temp1 + 1
		val = res
	while temp2 < y2:
		res = val + temp1 + temp2 - 1
		s = s + res
		temp2 += 1
		val = res
	print(s)


arr = [[0 for x in range(1001)] for y in range(1001)]
for i in range(1, 1001):
	arr[i][1] = i * (i + 1) // 2
	for j in range(2, 1001):
		arr[i][j] = arr[i][j - 1] + (j - 1) + (i - 1)
for T in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	total = 0
	for i in range(x1, x2 + 1):
		total += arr[i][y1]
	for j in range(y1 + 1, y2 + 1):
		total += arr[x2][j]
	print(total)


t = int(input())
for k in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	x1 = int(x1) - 1
	y1 = int(y1) - 1
	x2 = int(x2) - 1
	y2 = int(y2) - 1
	path = 1
	x = 0
	y = 0
	while x < x1:
		path += x + y + 2
		x += 1
	while y < y1:
		path += y + x1 + 1
		y += 1
	temp = path
	while x1 < x2:
		temp += x1 + y1 + 2
		path += temp
		x1 += 1
	while y1 < y2:
		temp += y1 + x2 + 1
		path += temp
		y1 += 1
	print(path)


t = int(input())

def formula(x, y):
	return (y - 1) * (2 * x + (y - 2)) // 2 + x * (x + 1) // 2
for i in range(t):
	(x1, y1, x2, y2) = [int(i) for i in input().split()]
	if x1 > x2 or (x1 == x2 and y1 > y2):
		(x1, x2) = (x2, x1)
		(y1, y2) = (y2, y1)
	s = 0
	while x1 <= x2:
		tmp = formula(x1, y1)
		s += tmp
		x1 += 1
	x1 -= 1
	y1 += 1
	while y1 <= y2:
		tmp = formula(x1, y1)
		s += tmp
		y1 += 1
	print(s)


t = int(input())
for i in range(t):
	(x, y, a, b) = map(int, input().split())
	e = []
	s = 0
	w = 0
	s = int(x * (x + 1) / 2)
	for j in range(2, y + 1):
		if j == y:
			w = s
		s = s + j - 1 + x - 1
	if w == 0:
		e.append(s)
		for j in range(x, a):
			s = (j + 1) * (j + 2) // 2
			e.append(s)
	else:
		w = s - w + 2
		e.append(s)
		for j in range(x, a):
			s += w
			e.append(s)
			w += 1
	for j in range(y + 1, b + 1):
		s += j - 1 + a - 1
		e.append(s)
	print(sum(e))


def value_at_xy(x, y):
	a = b = V = 1
	diff = 2
	while b != y:
		V += diff
		diff += 1
		b += 1
	diff -= 1
	while a != x:
		V += diff
		diff += 1
		a += 1
	return V

def path_value(x1, y1, x2, y2, V):
	ret = V
	diff = x1 + y1
	while y1 != y2:
		V += diff
		ret += V
		diff += 1
		y1 += 1
	diff -= 1
	while x1 != x2:
		V += diff
		ret += V
		diff += 1
		x1 += 1
	return ret
T = int(input())
for testcases in range(T):
	[y1, x1, y2, x2] = [int(x) for x in input().split()]
	S = value_at_xy(x1, y1)
	print(path_value(x1, y1, x2, y2, S))


mat = [[0] * 1004 for _ in range(1004)]
for i in range(1, 1004):
	mat[i][1] = i * (i + 1) // 2
	for j in range(2, 1004):
		mat[i][j] = mat[i][j - 1] + i + j - 2

def sol(x1, y1, x2, y2):
	s = 0
	for i in range(x1, x2 + 1):
		s += mat[i][y1]
	for i in range(y1 + 1, y2 + 1):
		s += mat[x2][i]
	return s
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	print(sol(x1, y1, x2, y2))


t = int(input())
for _ in range(t):
	arr = list(map(int, input().split()))
	x = arr[0]
	y = arr[1]
	x1 = arr[2]
	y1 = arr[3]
	n = 0
	for i in range(0, x):
		n += i + 1
	for i in range(0, y - 1):
		n += x + i
	s = n
	d = x + y
	for i in range(0, x1 - x):
		n += d + i
		s += n
	d = x1 + y - 1
	for i in range(0, y1 - y):
		n += d + i
		s += n
	print(s)