Olympiad in Informatics

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 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₁, j₁, i₂, j₂ representing the coordinates of a rectangle area in a puzzle: the top -left corner is (i₁, j₁) and the bottom-right corner is (i₂, j₂).

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