第 34 届国际数据结构奥林匹克竞赛即将举行！为了获得参赛资格，你需要通过你所在国家的队选拔赛。作为 Cat 队的一员，你需要在 Cat 队选拔赛中解决这道题。

在无限平面上有无数个整点，每个点都可以表示为 $(x, y)$。初始时，所有点的权值均为 0。你需要执行 $q$ 次操作，每次操作的形式如下：

• $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 \le x \le x_2$ 且 $y_1 \le y \le y_2$ 的点 $(x, y)$ 的权值之和。由于和可能很大，请输出其对 $2^{30}$ 取模的结果。

输入格式

第一行包含一个整数 $m$ ($1 \le m \le 10^5$)，表示操作次数。 接下来的 $m$ 行包含若干整数，格式如下：

• $1 \ x \ y \ d \ w$ ($1 \le x, y, d, w \le 10^8$)
• $2 \ x_1 \ x_2 \ y_1 \ y_2$ ($1 \le x_1 \le x_2 \le 10^8, 1 \le y_1 \le y_2 \le 10^8$)

输出格式

对于每个类型为 2 的操作，输出一行，包含一个整数：所求权值之和对 $2^{30}$ 取模的结果。

样例

输入 1

4
1 3 4 5 1
2 1 4 3 5
1 2 4 2 2
2 4 5 3 5

输出 1

46
21