4610 . Element Sum
Description
給定一個 $n\times m$ 的整數矩陣 $a$，左上角為 $(1, 1)$，右下角為 $(n, m)$，接下來有 $q$ 次查詢。
每次查詢給定左上角座標 $(x_1,y_1)$ 與右下角座標 $(x_2,y_2)$， 請計算並輸出矩形區域內所有元素的和。
Input Format
第一行包含三個正整數 $n,\ m,\ q$ $(1 \leq n, m \leq 1\,000,\ 1\leq q \leq 1\,000\,000)$。
接下來 $n$ 行，每行包含 $m$ 個整數，表示矩陣元素 $a_{i,j}$ $(-1\,000\,000 \leq a_{i, j} \leq 1\,000\,000)$。
接下來 $q$ 行，每行包含四個整數 $x_1,\ y_1,\ x_2,\ y_2$ $(1 \le x_1 \le x_2 \le n,\ 1 \le y_1 \le y_2 \le m)$。
Output Format
對於每個查詢，輸出一行，包含一個整數，表示對應區域的元素和。
Sample Input 1
3 5 1 3 1 4 1 5 4 8 7 6 3 1 2 4 8 6 1 2 3 4
Sample Output 1
41
Hints
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~23 | 無其他限制 | 100 |
