A08 - Two Dimensional Sum Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MiB

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