[Balkan2007]Mokia

维护一个 $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：表示输入结束。

输出格式

对于每个操作 2，输出一行，即该询问的答案。

样例输入

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

样例输出

3
5

样例解释

初始时矩阵全为 $0$。第一次操作把 $(2, 3)$ 的权值加 $3$，因此第一次询问的子矩阵内权值和为 $3$；随后 $(2, 2)$ 的权值加 $2$，第二次询问的子矩阵同时包含 $(2, 2)$ 与 $(2, 3)$，权值和为 $3+2=5$。

数据范围

• 修改操作数 $M\le 1.6\times 10^5$；
• 询问数 $Q\le 10^4$；
• $W\le 2\times 10^6$；
• 保证答案不会超过 int 范围。

来源与许可

本题为 Balkan 2007 试题「Mokia」，题面与测试数据整理自 BZOJ 1176。

样例 1

输入

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

输出

3
5