VBOARD - Chessboard

no tags 

Given a chessboard of size nxn. There is a number in each square of the board. The top-left 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 ith row and jth 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 ith line in the next n lines contains n integers ai1, ai2, ..., aij representing the numbers in the ith row of the chessboard (0 ≤ aij < 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 i1, j1, i2, j2 representing the coordinates of a rectangle area in a puzzle: the top -left corner is (i1, j1) and the bottom-right corner is (i2, j2).

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


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