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