## VBOARD - Chessboard

English | Vietnamese |

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
_{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 bottom-right 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

Input3 1 3 5 2 4 6 0 10 5 2 1 1 2 2 1 2 3 3Output0 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 |