Rize passed the entrance examination of Ecole Normale Super Paris. Her major is computer scienceand technology. She hopes to realize her dream of being a teacher in college and teach Chimame March to write code in the future.
One day, she wants to find all the sub-matrices of a matrix A, calculate the sum of the elements ofeach sub-matrix, and then add these sums to get the result. In other words, she wanted to ask for this:
Formally, a sub-matrix B of matrix A is a group of four integers u, d, l, r \ (1≤u≤d≤n; 1≤l≤r≤m). We will assume that the sub-matrix contains cells A_{i,j} \ (u≤i≤d;l≤j≤r). The area of the sub-matrix the number of cells it contains.
And Rize wrote the following code without hesitation:
But after Rize finished writing, she thought the code was too ugly. She observed that the final result is actually equivalent to multiplying each element by a constant, and then adding up the results. Soher code can be simplified as follows:
But Rize doesn’t know how to calculate this number. In other words, she does not know how toimplement the function get_const()
of the above code. She is stumped, and she hopes to solve thisproblem as soon as possible and then go to other topics. Can you help her?
输入
There is an integer Q \ (1≤Q≤10^5) in the first line, which means there are Q queries. Next Q lines,each line contains four integers x, y, n, m(1≤x≤n≤9 \times 10^4,1≤y≤m≤9 \times 10^4), representing theparameters of the function get_const()
.
输出
For each query, output an integer representing the return value of function get_const()
on a line
样例
标准输入 复制文本 |
3 2 2 3 3 1 3 4 5 50000 50000 50000 50000 |
标准输出 复制文本 |
16 36 2500000000 |
来源
SCNUCPC 2020 现场赛