【累積和メニュー】【二次元累積和】 二次元累積和 7 (paizaランク C)-解答例-PHP編

1 行目に整数 N, M, Q が与えられます。

2 行目以降に N 行 M 列の整数の二次元配列 A が与えられます。

2 + N 行目以降に Q 行に渡って整数 a_i, b_i, c_i, d_i (0 ≦ i ≦ Q - 1) が与えられます。

A の j 行目 k 列目を A_{j, k} (0 ≦ j ≦ N - 1, 0 ≦ k ≦ M - 1) と表すことにします。

i 番目の長方形領域の左上の要素を A_{a_i, b_i}, 右下の要素を A_{c_i, d_i} としたとき、これら Q 個の長方形領域内の整数の和を累積和を用いて求め、改行区切りで出力してください。

入力値（例）
5 5 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
1 1 3 3
2 2 4 4
0 0 2 2

出力値（例）
45
63
27