Model Evaluation
Description
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)$).
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$
Lines 1… $Q$: The value of $D$ for the given query
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
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
2
0
Note
$1<N≤800$
$1≤a_{i,j} ,b_{i,j}≤10^9$
$1≤r_1,c_1,r_2,c_2≤N$
$1<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.