Die 38. Internationale Olympiade für Datenstrukturen findet bald statt! Little Cyan Fish möchte sich qualifizieren und muss daher den Auswahlwettbewerb für das Nationalteam bestehen. Als Mitglied des Fish-Teams hat er beim Auswahlwettbewerb Fish Team Selection die folgende Aufgabe erhalten.

Im dreidimensionalen Raum gibt es unendlich viele Punkte $(x, y, z)$ mit ganzzahligen Koordinaten. Alle Punktgewichte betragen anfangs $0$. Little Cyan Fish muss der Reihe nach $q$ Operationen ausführen, jede in einer der folgenden Formen:

• 1 x y z d w: Für jeden Punkt $(X, Y, Z)$ mit $|X - x| < d$, $|Y - y| < d$ und $|Z - z| < d$ wird $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ zu seinem Gewicht addiert.
• 2 x1 x2 y1 y2 z1 z2: Gib das Gesamtgewicht der Punkte $(X, Y, Z)$ mit $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ und $z_1 \le Z \le z_2$ aus. Da die Summe groß sein kann, gib sie modulo $2^{28}$ aus.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $q$ ($1 \le q \le 5 \times 10^4$), die die Anzahl der Operationen angibt.

Jede der nächsten $q$ Zeilen enthält ganze Zahlen in einer der folgenden Formen:

• 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$).

Es wird garantiert, dass die Summe von $q$ über alle Testfälle $5 \times 10^4$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall für jede Operation vom Typ $2$ eine ganze Zahl in einer eigenen Zeile aus: die geforderte Summe der Punktgewichte modulo $2^{28}$. Gib die Antworten in der Reihenfolge der Operationen aus.

Beispiele

Eingabe 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

Ausgabe 1

28
2
4
31
0
0

Hinweis

Im ersten Testfall weist die erste Aktualisierung dem Ursprung das Gewicht $2$ und jedem der anderen $26$ Punkte in $[-1, 1]^3$ das Gewicht $1$ zu. Die zweite Aktualisierung addiert $3$ zum Punkt $(1, 1, 0)$.

Im zweiten Testfall betragen alle Gewichte anfangs wieder $0$.