SOLVE

LATER

Gold Mines

/

There is a rectangular grid of gold mine. The grid has **R** rows and **C** columns. So it has **R*C** cells in total. The rows are numbered from **1** to **R** and the columns are numbered from **1** to **C**. The top most row has number **1**, the row next to it has number **2** and so on. Similarly, the left most column has number **1**, the column next to it has number **2** and so on. Each cell in the grid has a unique coordinate which is **(x, y)** where x is the row number and y is the column number of that particular cell.

Each cell in the grid has certain amount of gold in it. Total gold in a sub rectangle of the grid is the sum of all units of gold contained in the cells that are inside the rectangle. Your task is to find the total gold in the given sub rectangle.

A sub rectangle of the grid is defined by **four** integers **x1**, **y1**, **x2** and **y2**. A cell **(x, y)** belongs to the sub rectangle if and only if **x1 <= x <= x2** and **y1 <= y <=y2**

**Input**

First line of the input contains two space separated integers, **R** and **C**. It is followed by **R** lines, each line has **C** space separated integers. Each integer denotes the units of gold present in that particular cell.

Next line has number **Q**, it is followed by **Q** queries each query in a single line. Each query is **four** space separated integers **x1**, **y1**, **x2** and **y2**.

**Output**

For each query, you have to print a single number the total gold contained in that sub rectangle.

**Constraints**

**1** <= **R** <= **1000**

**1** <= **C** <= **1000**

**1** <= **x1** <= **x2** <= **R**

**1** <= **y1** <= **y2** <= **C**

Amount of gold in each cell is an integer from **0** to **10^6**

Time Limit:
3.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...