题目描述

有一个 $W \times W$ 的矩阵，所有格子的初始值均为 $S$。

现在要对该矩阵进行一系列操作。

每次操作可以增加某格子的权值，或询问某子矩阵的总权值。

对于每个询问操作，请你输出被询问子矩阵的总权值是多少。

输入格式

第一行两个整数 $S, W$，其中 $S$ 为矩阵初始值，$W$ 为矩阵大小。

接下来每行为以下三种输入之一：

• 1 x y a —— 把第 $x$ 行第 $y$ 列的格子 $(x, y)$ 权值增加 $a$；
• 2 x1 y1 x2 y2 —— 询问以 $(x_1, y_1)$ 为左下角，$(x_2, y_2)$ 为右上角的矩阵内所有格子的权值和；
• 3 —— 输入结束。

注意：题目中坐标 $(x_1, y_1)$ 为左下角，$(x_2, y_2)$ 为右上角，这意味着 $x_1 \le x_2$，$y_1 \le y_2$。

输出格式

对于每个询问（即第二种输入），输出一行表示答案。

样例

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

3
5

样例解释

初始状态：
$S = 0, W = 4$，所有格子值为 $0$。

操作 1：1 2 3 3
将格子 $(2, 3)$ 增加 $3$，矩阵变为：

(1,1)=0 (1,2)=0 (1,3)=0 (1,4)=0
(2,1)=0 (2,2)=0 (2,3)=3 (2,4)=0
(3,1)=0 (3,2)=0 (3,3)=0 (3,4)=0
(4,1)=0 (4,2)=0 (4,3)=0 (4,4)=0

操作 2：2 1 1 3 3
查询左下角 $(1, 1)$ 到右上角 $(3, 3)$ 的子矩阵：

(1,1)=0 (1,2)=0 (1,3)=0
(2,1)=0 (2,2)=0 (2,3)=3
(3,1)=0 (3,2)=0 (3,3)=0

和为 $0+0+0+0+0+3+0+0+0 = 3$，输出 $3$。

操作 3：1 2 2 2
将格子 $(2, 2)$ 增加 $2$，矩阵变为：

(1,1)=0 (1,2)=0 (1,3)=0 (1,4)=0
(2,1)=0 (2,2)=2 (2,3)=3 (2,4)=0
(3,1)=0 (3,2)=0 (3,3)=0 (3,4)=0
(4,1)=0 (4,2)=0 (4,3)=0 (4,4)=0

操作 4：2 2 2 3 4
查询左下角 $(2, 2)$ 到右上角 $(3, 4)$ 的子矩阵：

(2,2)=2 (2,3)=3 (2,4)=0
(3,2)=0 (3,3)=0 (3,4)=0

和为 $2+3+0+0+0+0 = 5$，输出 $5$。

操作 5：3
结束程序。

数据范围

• 修改操作数 $M \le 160000$
• 询问次数 $Q \le 10000$
• $W \le 2000000$
• $1 \le a \le 10000$
• $1 \le x_1 \le x_2 \le W$
• $1 \le y_1 \le y_2 \le W$
• 所有数据的矩阵初始值 $S$ 均为 $0$

时间与空间限制

• 时间限制：2秒
• 空间限制：256MB

提示

由于 $W$ 最大可达 $2 \times 10^6$，直接开二维数组会超出内存限制，需要使用高效的数据结构（如树状数组或线段树）进行二维前缀和查询与单点更新。

注意：题目中坐标 $(x_1, y_1)$ 为左下角，$(x_2, y_2)$ 为右上角，实际计算时需要转化为标准的前缀和形式。