Submatrix Sum Queries

You are given an integer grid with R rows and C columns (1-indexed). Then you must answer Q queries. Each query gives the top-left corner (r1, c1) and bottom-right corner (r2, c2) of an axis-aligned rectangle, and asks for the sum of all grid values inside that rectangle, inclusive on all four sides. It is guaranteed that 1 ≤ r1 ≤ r2 ≤ R and 1 ≤ c1 ≤ c2 ≤ C for every query.

Input format

• Line 1: two integers R and C.
• The next R lines: each contains C space-separated integers — the grid, row by row.
• The next line: a single integer .

Output format

Print Q lines. Line i is the sum of the submatrix requested by the i-th query.

Constraints

• 1 ≤ R, C ≤ 1000
• 1 ≤ Q ≤ 200000
• Each grid value is between -1000000 and 1000000.
• 1 ≤ r1 ≤ r2 ≤ R and 1 ≤ c1 ≤ c2 ≤ C.