配点: 1000 点
問題文
H\times W 。从上面 i 行,从左起 j 列中的方块 (i, j) 是一个整数 写入 X_{i, j} 。 对此,现提出如下 编写一个程序来回答 Q 问题。
- i 问题:左上 (A_i, B_i) 右下 (C_i, D_i) 矩形区域中写入的整数之和是多少?
制約
- 1\leq H,W\leq 1500
- 1\leq Q\leq 100000
- 0\leq X_{i,j}\leq 9
- 1\leq A_i\leq C_i\leq H
- 1\leq B_i\leq D_i\leq W
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。 请输出超过
H W
X_{1, 1} X_{1, 2} \cdots X_{1, W}
\vdots
X_{H, 1} X_{H, 2} \cdots X_{H, W}
Q
A_1 B_1 C_1 D_1
\vdots
A_Q B_Q C_Q D_Q
出力
Q 行。i 行包含问题 请打印答案 i 。
入力例 1
5 5 2 0 0 5 1 1 0 3 0 0 0 8 5 0 2 4 1 0 0 6 0 9 2 7 0 2 2 2 4 5 1 1 5 5
出力例 1
25 56