Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

VBOARD - Chessboard

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:Jimmy
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 SCM qobi VB.NET
Resource:VNOI Marathon '08 - Round 2/DivB
Problem Setter: Ngô Minh Đức

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.