第 38 回国際データ構造オリンピックが間もなく開催されます！Little Cyan Fish は出場権を獲得したいと考えており、そのためには代表選抜コンテストに合格しなければなりません。Fish チームのメンバーである彼には、Fish チーム選抜コンテストで次の問題が与えられました。

3 次元空間内に、整数座標を持つ点 $(x, y, z)$ が無限個存在します。すべての点の重みは最初 $0$ です。Little Cyan Fish は $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 行に 1 つずつ出力してください。答えは操作の順番通りに出力してください。

入出力例

入力 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$ が与えられます。2 回目の更新では、点 $(1, 1, 0)$ に $3$ が加算されます。

2 番目のテストケースでは、すべての重みは再び初期状態で $0$ となります。