题目描述
你需要维护平面上的整点,每个点初始有点权 0,共 m 次操作。
修改操作:给定 x,y,d,w,将满足 |X−x|<d,|Y−y|<d 的整点 (X,Y) 的点权增加 w⋅(d−max;
查询操作:给定 x_1,x_2,y_1,y_2,查询满足 x_1\le X\le x_2,\;y_1\le Y\le y_2 的整点 (X,Y) 的点权之和,答案对 2^{30} 取模。
输入格式
从标准输入读入数据。
第一行一个整数 m,接下来 m 行,每行表示一个操作。
修改操作表示为 1 x y d w
;
查询操作表示为 2 x1 x2 y1 y2
。
输出格式
输出到标准输出。
对每个查询操作,输出一行,包含一个整数,表示取模后的答案。
样例数据
样例输入
5
1 3 4 5 1
2 1 4 3 5
1 2 4 2 2
2 4 5 3 5
1 4 4 4 8
样例输出
46
21
子任务
对于 23\% 的数据,满足 1\le m\le 10^3。
对于 31\% 的数据,满足 1\le m\le 2\times 10^4。
对于 39\% 的数据,满足 1\le m\le 4\times 10^4。
对于 47\% 的数据,满足 1\le m\le 6\times 10^4。
对于 55\% 的数据,满足 1\le m\le 8\times 10^4。
对于另外 15\% 的数据,满足对任意询问操作,不存在一个修改操作,该修改操作在该询问操作之后。
对于另外 10\% 的数据,满足 x_2-x_1\le 5,y_2-y_1\le 5,d\le 5。
对于另外 10\% 的数据,满足 d\le 5。
对于 100\% 的数据,满足 1\le m\le 10^5,1\le x_1\le x_2\le {10}^8,1\le y_1\le y_2\le {10}^8,1\le x,y,d,w\le {10}^8。
每类数据构成子任务。