题目描述

有一个 $W$×$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—输入结束。

输出格式

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

样例

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

3
5

数据范围

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

来源

• BZOJ1176
• 算法竞赛进阶指南