## Market Analysis

View as PDF

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

Author:
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 by blocks. Associated with each block is a viability . The MoonBucks Corporation has 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 to , inclusive and the columns to , inclusive. Do note that rows are numbered from to from top to bottom and columns are numbered to from left to right in the input.

#### Input Specifications

The first line contains three integers, , , and , respectively.

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

The next lines contain each contain 4 integers, , , , and

#### Output Specifications

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