seuOJ234 - 小雅米的魔法阵

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：6000 ms
• 空间限制：256 MiB
• 题目标签：秋季, 校赛, 2019

题目描述

小雅米有一块由 $n \times m$ 块魔法石头组成的 $n$ 行 $m$ 列魔法阵。起初，第 $i$ 行的第 $j$ 块石头有能量 $a_{ij}$，每块石头每秒流失能力 $1$ 点，能量流失至 $0$ 时便不再流失。小雅米对这个魔法阵十分好奇他会提出 $q$ 个问题，第 $i$ 个问题是在 $t_i$ 秒后，以$(x_{i1},y_{i1})$ 为左下角，$(x_{i2},y_{i2})$ 为右上角的矩形中共有多少能量。

输入格式

第一行一个整数 $T(1\leq T\leq 3)$ 代表数据组数。

每组数据第一行三个正整数 $n,m,q(1\leq n,m\leq 10^3,1\leq q \leq 10^5)$。

下面 $n$ 行每行 $m$ 个正整数,代表初始时每块能量石头的能量 $a_{ij}(0 \leq a_{ij} \leq 10^6)$。

下面 $q$ 行每行五个数字 $t,x_{i1},y_{i1},x_{i2},y_{i2}(0 \leq t \leq 10^6,1 \leq x_{i1} \leq x_{i2} \leq n,1 \leq y_{i1} \leq y_{i2} \leq m)$ 代表询问 $t$ 时刻以 $(x_{i1},y_{i1})$ 为左下角，$(x_{i2},y_{i2})$ 为右上角的矩形中共有多少能量。

输出格式

每组数据 $q$ 行，每行一个正整数代表每次询问的结果。

样例

输入样例

1
3 4 5
1 2 3 4
4 3 2 1
5 5 5 5
5 1 1 3 4
0 1 1 3 4
1 1 1 3 4
2 2 2 3 3
3 2 2 3 4

输出样例

0
40
28
7
6