题目描述

需维护平面上的整点，所有点初始点权为 $0$，共 $m$ 次操作，分为两类：

1. 修改操作：给定 $x,y,d,w$，对满足 $|X-x| < d$ 且 $|Y-y| < d$ 的所有整点 $(X,Y)$，将其点权增加 $w \cdot (d - \max(|X-x|, |Y-y|))$；
2. 查询操作：给定 $x_1,x_2,y_1,y_2$，计算满足 $x_1 \leq X \leq x_2$ 且 $y_1 \leq Y \leq y_2$ 的所有整点 $(X,Y)$ 的点权之和，结果对 $2^{30}$ 取模。

输入格式

从标准输入读入数据，格式如下：

1. 第一行：一个整数 $m$（操作总次数）；
2. 接下来 $m$ 行：每行表示一次操作：
   • 若为修改操作，格式为 1 x y d w（$1 \leq x,y,d,w \leq 10^8$）；
   • 若为查询操作，格式为 2 x1 x2 y1 y2（$1 \leq x1 \leq x2 \leq 10^8$，$1 \leq y1 \leq y2 \leq 10^8$）。

输出格式

输出到标准输出，对每个查询操作，输出一行整数，表示该查询的结果（对 $2^{30}$ 取模）。

样例

输入

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

样例解释

1. 第一次修改操作（$x=3,y=4,d=5,w=1$）：对 $X \in (-2,8)$、$Y \in (-1,9)$ 的整点，按规则增加权值；
2. 第一次查询（$X \in [1,4], Y \in [3,5]$）：计算该矩形内所有点的权值和，结果为 $46$；
3. 第二次修改操作（$x=2,y=4,d=2,w=2$）：对 $X \in (0,4)$、$Y \in (2,6)$ 的整点，按规则增加权值；
4. 第二次查询（$X \in [4,5], Y \in [3,5]$）：计算该矩形内所有点的权值和，结果为 $21$；
5. 第三次修改操作无后续查询，无需输出。

数据范围与提示