# 分批更新的矩形最大值

时间限制：4 秒；内存限制：512 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见[评测环境](../../../docs/评测环境与性能.md)。

## 背景故事

温室管理员用一个矩形网格记录各区的温度偏差。传感器会成批上传区域修正，管理员则查询一块区域内的最大偏差，决定下一轮通风安排。

(本故事由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

### 输入

```text
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
```

### 输出

```text
5
10
2
```

## 样例 2

### 输入

```text
1 1 3
-20000
1 1 1 1 1 -20000
2 1 1 1 1
2 1 1 1 1
```

### 输出

```text
-40000
-40000
```

## 样例 3

### 输入

```text
1 3 3
0 10 20
1 1 1 1 3 3
2 1 2 1 2
2 1 1 1 3
```

### 输出

```text
13
23
```

## 样例解释

样例1经过两次修改后，矩阵两行分别为 $[1,5,10]$ 和 $[-6,2,1]$ .全局最大值为10，第二行最大值为2。样例2说明答案可以为负数。

![示意图](assets/example.svg)

样例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%；完整配方见[测试说明](tests/README.md)。