CHESSBOARD - Simple Sum

Mr. Puede likes to play chess. Not just ordinary chess, but this one is special. The chessboard with maximum length N2. Suddenly he wants to putting numbers on his chessboard and to count the sum of black squares and white squares in a certain box area. Because he doesn't really understand about mathematics, please write a program to him solve his problems.

Note : top left corner is white square.

Input

First line N (2 <= N <= 500) is the number of length and width of the chessboard. The next N lines consist of numbers inside the chessboard (1 <= X <= 1000). Then followed by Q query (1 <= Q <= 10000). Each of Q lines consist of 4 number indicate the coordinate of top left corner and bottom right corner from the rectangle. 

Output

Print the difference between sum of black squares and white squares in absolute (non negative number) from each query.

Example

Input:
3
1 3 5
2 4 6
0 10 5
2
1 1 2 2
2 2 3 3 Output:
0
7

Added by:wibit
Date:2020-04-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C NCSHARP C++ 4.3.2 JULIA PYPY3
Resource:Own Problem

hide comments
2024-08-26 13:29:28
ac in one go using microsoft paint
2021-12-27 08:34:43
ac in one go using microsoft power point
2020-12-07 06:52:23 wibit
input and output already clarify that indexing array starting from 1 :)
2020-04-30 14:28:57
@wibit, plz look into the problem once.
No matter how many times I submitted, it is giving compilation error!!
I mean if it was wrong answer then I would have checked my solution but my code is running perfectly fine on ideone and I don't think that the compiler will be changed so much from ideone.

Edit: The code written in C is only accepted.
Also, I have some suggestions.
Plz state in your problem statement that the indexing of the top-left and bottom-right corners is starting from 1.

Last edit: 2020-04-30 14:36:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.