「Mokia」 莫基亚

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

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

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

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

输入格式

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

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

“$1\ x\ y\ a$”——把第 $x$ 行第 $y$ 列的格子 $(x,y)$ 权值增加 $a$；
“$2\ x_1\ y_1\ x_2\ y_2$”——询问以 $(x_1,y_1)$ 为左下角，$(x_2,y_2)$ 为右上角的矩阵内所有格子的权值和；
“$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$，

输入样例：

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

输出样例：

3
5

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解