题目描述

你需要维护平面上的整点，每个点初始有点权 $0$，共 $m$ 次操作。

修改操作：给定 $x,y,d,w$，将满足 $|X-x| < d,|Y-y| < d$ 的整点 $(X,Y)$ 的点权增加 $w\cdot(d-\max(|X-x|,|Y-y|))$；

查询操作：给定 $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$。

每类数据构成子任务。