题目描述

给定一个有 $n$ 行、$m$ 列的整数矩阵 $a$，执行 $q$ 次操作：

• 修改：将单元格 $a[x][y]$ 赋值为 $v$（不是加上 $v$）。
• 查询：计算矩形左上角 $(x_1,y_1)$ 到右下角 $(x_2,y_2)$ 之间的所有元素之和，包含四条边界。

输入格式

第一行输入三个整数 $n,m,q$，分别表示矩阵行数、列数和操作次数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示初始矩阵。

接下来 $q$ 行，每行表示一条操作：

• 1 x y v：将 $a[x][y]$ 修改为 $v$。
• 2 x1 y1 x2 y2：查询行号在 $[x_1,x_2]$、列号在 $[y_1,y_2]$ 内的元素之和。

输出格式

每次遇到操作 2，输出一行整数表示当前矩形元素和。操作 1 不产生输出。

输入输出样例

输入

5 5 3
3 0 1 4 2
5 6 3 2 1
1 2 0 1 5
4 1 0 1 7
1 0 3 0 5
2 2 1 4 3
1 3 2 2
2 2 1 4 3

输出

8
10

数据范围

• $1\le n,m\le 200$
• $1\le q\le 5000$（该改写版本至少有一个操作；原 LeetCode 题只限制最多 5000 次）
• $-1000\le a[i][j],v\le1000$
• $0\le x,x_1\le x_2<n$
• $0\le y,y_1\le y_2<m$

所有操作输入保证合法。无额外的测试点分组得分比例限制。