Block sums in a table

Problem

A table has R rows and C columns of sales figures. For each query give the sum of the block from row r1, column c1 to row r2, column c2, with all corners included. Rows and columns are numbered from 0.

Input, output and limits

Input: The first line has R and C. The next R lines have C integers each. Then a line with q, and q lines with r1, c1, r2 and c2.
Output: q lines, one sum per query.
Constraints: 1 ≤ R, C ≤ 300
1 ≤ q ≤ 10000
-1000 ≤ each figure ≤ 1000
0 ≤ r1 ≤ r2 < R and 0 ≤ c1 ≤ c2 < C

Examples

Example

Input

Output

14
3

The block sums to 14. The single cell is 3.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Build a table of corner totals once, with an extra row and column of zeros.

Hint 2

A block is the big corner, minus the strip above, minus the strip on the left, plus the corner removed twice.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems