2D Prefix Sum - Classic Problems | Repovive

CLS37. 2D Prefix Sum

2s256 MB

Given an $n \times m$ grid of integers and $q$ queries, answer each query asking for the sum of elements in a submatrix.

Each query specifies the top-left corner $(r_1, c_1)$ and bottom-right corner $(r_2, c_2)$ of the submatrix (1-indexed).

Constraints

$1 \le n, m \le 500$
$1 \le q \le 10^5$
$0 \le a_{i,j} \le 10^6$
$1 \le r_1 \le r_2 \le n$
$1 \le c_1 \le c_2 \le m$

Input

\begin{array}{l} n \quad m \quad q \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad \text{(query 1)} \\ \vdots \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad \text{(query } q \text{)} \end{array}

Output

\begin{array}{l} S_1 \\ S_2 \\ \vdots \\ S_q \end{array}

Samples

Input

Explanation

The first query covers 1, 2, 4, and 5, whose sum is 12. The second query covers the whole grid, whose sum is 45. The third query covers 5, 6, 8, and 9, whose sum is 28.

Output

12
45
28

Input

Explanation

The first two queries ask for single cells with values 5 and 8. The last query asks for the whole grid, so 5 + 3 + 2 + 8 = 18.

Output

5
8
18

Input

Explanation

Every grid value is 1. The first query covers one row of 4 cells, the second covers one column of 3 cells, and the last covers all 12 cells.

Output

4
3
12

Given an $n \times m$ grid of integers and $q$ queries, answer each query asking for the sum of elements in a submatrix.

Each query specifies the top-left corner $(r_1, c_1)$ and bottom-right corner $(r_2, c_2)$ of the submatrix (1-indexed).

$1 \le n, m \le 500$
$1 \le q \le 10^5$
$0 \le a_{i,j} \le 10^6$
$1 \le r_1 \le r_2 \le n$
$1 \le c_1 \le c_2 \le m$

\begin{array}{l} n \quad m \quad q \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad \text{(query 1)} \\ \vdots \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad \text{(query } q \text{)} \end{array}

\begin{array}{l} S_1 \\ S_2 \\ \vdots \\ S_q \end{array}