分批更新的矩形最大值¶
时间限制：4 秒；内存限制：512 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见评测环境。
背景故事¶
温室管理员用一个矩形网格记录各区的温度偏差。传感器会成批上传区域修正，管理员则查询一块区域内的最大偏差，决定下一轮通风安排。
(本故事由GPT-6重写)
形式化问题描述¶
给定 \(n\) 行 \(m\) 列的整数矩阵，依次处理 \(Q\) 个操作：
1 x1 y1 x2 y2 v：给闭矩形 \([x_1,x_2]\times[y_1,y_2]\) 内每个单元格加上 \(v\) .2 x1 y1 x2 y2：输出该闭矩形内的最大值。
行列下标都从1开始，端点有序。矩阵值和增量可以为负数。极大连续修改段指操作序列中连续的一段类型1操作，且不能向前或向后再扩展一个类型1操作。这样的段数最多为20；相邻查询之间可以有任意多次修改。
输入格式¶
第一行 n m Q .接下来 \(n\) 行，每行 \(m\) 个初始值。接下来 \(Q\) 行，每行是上述一种操作。
输出格式¶
每个类型2操作输出一行一个整数。
样例 1¶
输入¶
2 3 5
1 -2 3
4 5 -6
2 1 1 2 3
1 1 2 2 3 7
1 2 1 2 2 -10
2 1 1 2 3
2 2 1 2 3
输出¶
5
10
2
样例 2¶
输入¶
1 1 3
-20000
1 1 1 1 1 -20000
2 1 1 1 1
2 1 1 1 1
输出¶
-40000
-40000
样例 3¶
输入¶
1 3 3
0 10 20
1 1 1 1 3 3
2 1 2 1 2
2 1 1 1 3
输出¶
13
23
样例解释¶
样例1经过两次修改后，矩阵两行分别为 \([1,5,10]\) 和 \([-6,2,1]\) .全局最大值为10，第二行最大值为2。样例2说明答案可以为负数。
样例1的初始矩阵和完成两次修改后的矩阵。
数据范围与分值¶
\(1\le n,m\) ，\(nm\le10^7\) ，\(1\le Q\le10^5\) ，\(|a_{ij}|,|v|\le20000\) ，\(1\le x_1\le x_2\le n\) ，\(1\le y_1\le y_2\le m\) .极大连续修改段数不超过20。
| 分值 | 额外限制 |
|---|---|
| 20% | \(nm\le100,\ Q\le100\) |
| 30% | \(nm\le10^5,\ Q\le5000\) |
| 50% | 无额外限制 |
共10个测试点，每点占10%；完整配方见测试说明。