You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

《以撒》是一款优秀的随机地牢游戏，玩家将扮演以撒用眼泪与地下室的怪物们进行战斗。《以撒》地图可看作 $N \times M$ 的网格，每个格子中有若干敌人。

现在玩家会频繁使用「扫描」道具，扫描一个矩形区，你需要立刻返回该矩形内敌方数量。

地图在战斗开始后不会变化，但扫描请求非常多。

输入格式

第一行三个整数 $N, M, Q$，分别表示地图的行数、列数和扫描请求次数。

接下来 $N$ 行，每行 $M$ 个整数，表示每个格子的敌方人数。

接下来 $Q$ 行，每行四个整数 $x_1, y_1, x_2, y_2$，表示查询矩形左上角 $(x_1, y_1)$、右下角 $(x_2, y_2)$。

坐标从 $1$ 开始，保证 $x_1 \le x_2$，$y_1 \le y_2$。

输出格式

输出 $Q$ 行，每行一个整数，表示该矩形区域内的总敌人数。

测试用例

3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 2 2
2 2 3 4
1 3 3 3

14
54
21

数据规模与约定

1s, 256MiB for each test case.

· $1 \le N, M \le 2000$ · $1 \le Q \le 200000$ · 每个格子的战力绝对值不超过 $10^9$ · 答案可能超过 32 位整数