Mr. Puede likes to play chess. Not just ordinary chess, but this one is special. The chessboard with maximum length N². 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