第 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$。