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

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

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

输出格式

对每个查询操作，输出一行，包含一个整数，表示取模后的答案。

样例数据

样例 1 输入

8
1 8 10 2 2
2 1 5 3 4
1 8 5 7 10
1 1 5 4 10
1 4 2 1 1
1 8 5 8 9
2 2 6 2 9
1 8 9 2 3

样例 1 输出

0
61

子任务

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $25\%$ 的数据，满足 $m,x_1,x_2,y_1,y_2,x,y,d,w\le 50$。

对于另外 $25\%$ 的数据，满足 $m\le 2000$。

对于另外 $25\%$ 的数据，满足修改操作在所有查询操作之前。

对于 $100\%$ 的数据，满足 $1\le m\le 2\times 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$。