2.方阵问题

题目描述

给定一个$n \times m$的方阵，共$n$行，每行$m$个值。

给定$q$个操作，每次对一个子矩阵进行求和或求最大值/最小值。

输入格式

第一行包含两个正整数$n$，$m$。

接下来$n$行，每行$m$个非负整数，这其中的第$i$行第$j$个数$a_{i,j}$，表示第$i$行第$j$个值。

接下来一行包含一个整数$q$，表示询问次数。

接下来$q$行，每行先一个字符串$s$，接下来$4$个整数$x_1$，$y_1$，$x_2$，$y_2$。

设以第$x_1$行第$y_1$列为左上角，第$x_2$行$y_2$列为右下角的方阵为$P$（位置从$0$开始计数）。

• 若字符串为$SUM$，请求出$P$中所有的权值之和。
• 若字符串为$MAX$，请求出$P$中所有的权值的最大值。
• 若字符串为$MIN$，请求出$P$中所有的权值的最小值。

输出格式

输出总共$q$行，第$i$行的数为第$i$组的询问答案。

数据范围与提示

• 对于$40\%$的数据，$n,m \leq 200$，$q \leq 200$；
• 对于$60\%$的数据，$n,m \leq 300$，$q \leq 100000$；
• 对于$80\%$的数据，$n,m \leq 500$，$q \leq 500000$；
• 对于$100\%$的数据，$n,m \leq 800$，$q \leq 500000$，$0 \leq A_{i,j} \leq 3000$，$0 \leq x_1 \leq x_2 < n$，$0 \leq y_1 \leq y_2 < m$，且每个询问的方阵的较长边不超过较短边的两倍。

样例

3 3
1 2 3
4 5 6
7 8 9
3
SUM 0 0 1 1
MAX 0 0 2 2
MIN 0 1 1 1

12
9
2