The MoonBucks Corporation is hoping to build a new store! They would like you to perform some market analysis and figure out the most optimal location to place the store.

The city they are considering can be represented by a grid of ~N~ by ~M~ blocks. Associated with each block is a viability ~v_{ij}~. The MoonBucks Corporation has ~K~ potential stores. Each store will cover a "rectangle" of blocks and will have a yearly profit equal to the sum of the viability of each block inside the rectangle. For each potential store, please provide The MoonBucks Corporation with the yearly profit expected from it.

For each store, the rectangle it covers is described as the rectangle from rows ~a_i~ to ~b_i~, inclusive and the columns ~c_i~ to ~d_i~, inclusive. Do note that rows are numbered from ~1~ to ~N~ from top to bottom and columns are numbered ~1~ to ~M~ from left to right in the input.

Constraints

~1\le N, M\le 1000~

~1\le K\le 10^5~

~1\le v_{ij}\le 1000~

~1\le a_i\le b_i\le N~

~1\le c_i \le d_i \le M~

Input Specifications

The first line contains three integers, ~N~, ~M~, and ~K~, respectively.

The next ~N~ lines each contain ~M~ integers, describing the grid of the city.

The next ~K~ lines contain each contain 4 integers, ~a_i~, ~b_i~, ~c_i~, and ~d_i~

Output Specifications

~K~ lines with one integer each. For each line, output the yearly profit of each store.

Sample Input

3 5 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
1 2 1 3
1 3 1 1
1 3 1 5
1 2 4 5

Sample Output

15
6
60
20

Sample Explanation

For the first query, the queried rectangle is made up of the top two rows and the left 3 columns - the rectangle looks as such:

1 2 3
2 3 4

So, the sum of values is ~1+2+3+2+3+4=15~