← 返回题目列表

AtCoder · tessoku_book_h

A08. 二维和

中文机器翻译题面 查看原题

配点: 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