VBOARD  Chessboard
English  Vietnamese 
Given a chessboard of size nxn. There is a number in each square of the board. The topleft square is in white color (the squares are in black and white color alternatively). The columns are numbered as 1 to n from left to right. The rows are number as 1 to n from top to bottom. The square in the i^{th} row and j^{th} column of the board is denoted as (i, j).
Cuoi have some puzzles for Bom: Cuoi tells Bom a rectangle area in the chessboard, and Bom has to calculate the absolute value of the difference between the sum of white squares' numbers and the sum of black squares' numbers in that area. Help Bom to answer these puzzles.
Input
 The first line contains an integer n (1 ≤ n ≤ 500).
 The i^{th} line in the next n lines contains n integers a_{i1}, a_{i2}, ..., a_{ij} representing the numbers in the i^{th} row of the chessboard (0 ≤ a_{ij} < 100).
 The (n+2)^{th} row contains an integer q that is the number of Cuoi's puzzles (1 ≤ q ≤ 10000).
 Each line in the next q lines contains four integers i_{1}, j_{1}, i_{2}, j_{2} representing the coordinates of a rectangle area in a puzzle: the top left corner is (i_{1}, j_{1}) and the bottomright corner is (i_{2}, j_{2}).
Output
Print out q lines; in each line, print Bom's answer to Cuoi's corresponding puzzle.
Constraint
There are 50% of the test cases corresponding to 50% of the grades in which 1 ≤ n ≤ 100 and 1 ≤ q ≤ 2000.
Example
Input 3 1 3 5 2 4 6 0 10 5 2 1 1 2 2 1 2 3 3 Output 0 5
hide comments
richardks3647:
20180818 04:15:09
100 in one go using chess board 

pigpork:
20180704 03:03:34
Expand c (a + b)

Added by:  Jimmy 
Date:  20080618 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  VNOI Marathon '08  Round 2/DivB Problem Setter: Ngô Minh Đức 