Problem E

在数据维护的过程中，保持高效的数据访问和修改是非常重要的工作，这个题目就需要你用高效的手段来维护一段数据并执行不同的操作。

我们首先用如下公式生成一个矩阵A：

A_{i, j} = i + j

这里1 <= i <= N, 1 <= j <= M，其中N和M为给定的参数。
接下来你需要处理如下操作：

1. M i j v: 修改元素A_{i, j}的值为v(1 <= i <= N, 1 <= j <= M, 1<=v<= N+M);
2. Q p q r s: 查询以A_p,q和A_r,s为对角元素的子矩阵的和(1<=p<=r<=N, 1<=q<=s<=M)。

对于每组询问请输出它的答案。

注：在这个题目中，对矩阵的修改（即第一种操作）的次数不会超过10次。

输入的第一行是测试数据的组数T (T<=20)。
对于每组测试数据：
第一行是矩阵的行数N，列数M和操作的数量Q (1<= N, M, Q <= 10^3).

接下来Q行按顺序给出了所有操作。每一个操作的格式都如上所述，并且对矩阵的修改次数不会超过10次。

对于每次查询，输出相应的子矩阵的和。

1
3 4 4
Q 1 1 1 1
Q 1 1 3 2
M 1 1 3
Q 1 1 3 4

2
21
55

In sample, the original matrix A should satisfy:

校第十六届大学生程序设计竞赛暨2016省赛集训队选拔赛