題目描述

有 n 行 m 列的矩陣 A，下標從 1 開始。

接下來有 q 次查詢，每次查詢輸入 4 個參數 x₁, y₁, x₂, y₂。

請輸出以 ( x₁, y₁ ) 為左上角，( x₂, y₂ ) 為右下角的子矩陣和。

輸入格式

第一行三個正整數 n, m , q。

接著 n 行，每行 m 個整數，表示矩陣的元素值。

接著 q 行，每行 4 個正整數 x₁, y₁, x₂, y₂，表示查詢參數。

輸出格式

輸出 q 行，每行表示查詢結果。

Samples

3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4

8
25
32

提示

1 ≤ n, m ≤ 1000
1 ≤ q ≤ 10⁵
−10⁹ ≤ a[i][j] ≤ 10⁹
1 ≤ x₁ ≤ x₂ ≤ n
1 ≤ y₁ ≤ y₂ ≤ m

原始資料

• Zero1 題號：b221
• Hydro 題號：Z1221
• Locale：zh_TW
• Display：practice