H. Model Evaluation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sara has trained an AI model to generate pictures of kittens given certain verbal prompts. As a very basic form of evaluation for her model, she decides to take the absolute value of the difference $$$D$$$ between the sums of all pixels in a region of the image $$$A$$$ her model generates and the real-life reference photo $$$B$$$ that she chooses. $$$A$$$ and $$$B$$$ are both square images $$$N$$$ pixels long on each side.

Given $$$Q$$$ queries consisting of two pairs of coordinates $$$(r_1,c_1)$$$ and $$$(r_2,c_2)$$$, print out the value of $$$D$$$ for the rectangular regions in $$$A$$$ and $$$B$$$ bounded by $$$(r_1,c_1)$$$ and $$$(r_2,c_2)$$$ (including $$$(r_1,c_1)$$$ and $$$(r_2,c_2)$$$).

Input

Line 1: Two space separated integers $$$N$$$,$$$Q$$$

Lines 2… $$$N+1$$$: $$$N$$$ space separated integers $$$a_1...a_N$$$, representing image $$$A$$$

Lines $$$N+2$$$... $$$2N+1$$$: $$$N$$$ space separated integers $$$b_1...b_N$$$, representing image $$$B$$$

Lines $$$2N+2$$$… $$$2N+Q+1$$$: Four space separated integers $$$r_1,c_1,r_2,c_2$$$

Output

Lines 1… $$$Q$$$: The value of $$$D$$$ for the given query

Example
Input
3 2
3 1 7
2 5 2
5 8 4
5 2 2
1 3 7
4 9 4
1 1 1 3
3 3 1 2
Output
2
0
Note

$$$1 \lt N≤800$$$

$$$1≤a_{i,j} ,b_{i,j}≤10^9$$$

$$$1≤r_1,c_1,r_2,c_2≤N$$$

$$$1 \lt Q≤70000$$$

The sum of pixel values in $$$A$$$ and $$$B$$$ in the region enclosed by $$$(1,1)$$$ and $$$(1,3)$$$ are 3+1+7=11 and 5+2+2=9 respectively, so $$$D$$$ is equal to 2.

The sum of pixel values in $$$A$$$ and $$$B$$$ in the region enclosed by $$$(3,3)$$$ and $$$(1,2)$$$ are 1+7+5+2+8+4=27 and 2+2+3+7+9+4=27 respectively, so $$$D$$$ is equal to sum of pixel values is 0.