Market Analysis

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem type

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.


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


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


There are no comments at the moment.