問題文

縦 $H$ 行、横 $W$ 列のマス目があります。

各マスには $1$ 個の整数が書かれており、上から $i (1 \leq i \leq H)$ 行目、左から $j (1 \leq j \leq W)$ 列目のマスには整数 $X_{ij}$ が書かれています。

質問が $Q$ 個与えられるので、各質問に対する答えを出力してください。$i(1 \leq i \leq Q)$ 個目の質問は以下のような質問です。

• 整数 $A_i,B_i,C_i,D_i (1 \leq A_i \leq C_i \leq H,1 \leq B_i \leq D_i \leq W)$ が与えられます。以下の式の値を求めてください。

制約

• $1 \leq H,W \leq 1000$
• $1 \leq Q \leq 1000$
• 各 $i(1 \leq i \leq H),j(1 \leq j \leq W)$ に対し、 $-100 \leq X_{ij} \leq 100$
• 各 $i(1 \leq i \leq Q)$ に対し、 $1 \leq A_i \leq C_i \leq H,1 \leq B_i \leq D_i \leq W$
• 入力は全て整数

入力

出力

各質問に対する答えを $1$ 行ずつ出力してください。

サンプル

3 3
1 2 3
4 5 6
7 8 9
3
1 2 2 3
2 2 2 2
1 1 3 3

16
5
45