除了攻擊魔法和防禦魔法外，還有大量形形色色的輔助魔法，只是平時很少受到重視。

就像一般學術大學會要求學生修一定學分的通式課，Leo 在魔法學院裡也要學習各種輔助魔法。

這次考核的題目是「偵測魔法」，這個魔法可以取得一個 $M \times N$ 矩形範圍內的生命反應數量和位置，沒生命反應的地方標示為 0，有生命反應的地方則依人數標示為一個正整數 $W，(1 \le W \le 1000)$。

對於部隊來說是個非常重要的情報來源，但是取得資訊是一回事，能有效運用這個資訊才是重點。

對於情報官來說，能快速提供將領們查詢指定範圍內生命反應人數是致勝的重要關鍵，這也是魔法師的重要跨領域能力。

Leo 必須快速在偵測魔法回傳的矩形資料中，做多次統計，算出將領指定矩形區域中，共有多少人的生命反應。

例如，偵測魔法傳回了一個 4 x 5 的矩形資料如下，左上角座標為 (1, 1)，右下角座標為 (4,5)

1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2

將領要求 3 次查詢

第一次查詢矩形範圍的左上角 (r1, c1)= (1, 1) 與右下角 (r2, c2) = (4, 5)

1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2

應回覆 70

第一次查詢矩形範圍的左上角 (r1, c1)= (2, 2) 與右下角 (r2, c2) = (3, 4)

1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2

應回覆 21

第一次查詢矩形範圍的左上角 (r1, c1)= (1, 3) 與右下角 (r2, c2) = (3 5)

1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2

應回覆 33

子任務說明

子任務1：
範例測資

子任務2：
$1 \le N, M \le 100$
$1 \le Q \le 100$

子任務3：
$1 \le N, M \le 1,000$
$1 \le Q \le 10,000$

子任務4：
沒有題目敘述(含輸入格式 Input Format 說明)之外的限制