第 38 届国际数据结构奥林匹克竞赛即将举行！小青鱼想要获得参赛资格，因此他必须通过国家队选拔赛。作为鱼队的一员，他在鱼队选拔赛中遇到了下面这道题。

在三维空间中，有无穷多个具有整数坐标的点 $(x, y, z)$。所有点的权值初始均为 $0$。小青鱼必须按顺序执行 $q$ 次操作，每次操作的形式如下：

• 1 x y z d w：对于每个满足 $|X - x| < d$、$|Y - y| < d$ 且 $|Z - z| < d$ 的点 $(X, Y, Z)$，将其权值加上 $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$。
• 2 x1 x2 y1 y2 z1 z2：输出所有满足 $x_1 \le X \le x_2$、$y_1 \le Y \le y_2$ 且 $z_1 \le Z \le z_2$ 的点 $(X, Y, Z)$ 的总权值。由于总权值可能很大，请输出其对 $2^{28}$ 取模的结果。

输入格式

本题包含多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T$），表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $q$（$1 \le q \le 5 \times 10^4$），表示操作的数量。

接下来 $q$ 行，每行包含以下形式之一的若干个整数：

• 1 x y z d w（$-10^9 \le x, y, z \le 10^9$，$1 \le d \le 10^9$，$0 \le w < 2^{28}$）。
• 2 x1 x2 y1 y2 z1 z2（$-10^9 \le x_1 \le x_2 \le 10^9$，$-10^9 \le y_1 \le y_2 \le 10^9$，$-10^9 \le z_1 \le z_2 \le 10^9$）。

保证所有测试数据中 $q$ 的总和不超过 $5 \times 10^4$。

输出格式

对于每组测试数据，针对每个类型为 $2$ 的操作，在单独的一行中输出一个整数：所求点权总和对 $2^{28}$ 取模的结果。请按照操作的顺序依次输出答案。

样例

输入格式 1

2
7
1 0 0 0 2 1
2 -1 1 -1 1 -1 1
2 0 0 0 0 0 0
1 1 1 0 1 3
2 1 1 1 1 0 0
2 -1 1 -1 1 -1 1
2 2 2 0 0 0 0
1
2 0 0 0 0 0 0

输出格式 1

28
2
4
31
0
0

说明

在第一组测试数据中，第一次修改使原点的权值变为 $2$，并使 $[-1, 1]^3$ 中其余 $26$ 个点的权值均变为 $1$。第二次修改将点 $(1, 1, 0)$ 的权值加上 $3$。

在第二组测试数据中，所有点的权值初始再次均为 $0$。