Już wkrótce odbędzie się 38. Międzynarodowa Olimpiada Struktur Danych! Little Cyan Fish chce się zakwalifikować, więc musi pomyślnie przejść eliminacje do reprezentacji narodowej. Jako członek drużyny Fish otrzymał następujące zadanie podczas konkursu Fish Team Selection.

W przestrzeni trójwymiarowej istnieje nieskończenie wiele punktów $(x, y, z)$ o współrzędnych całkowitych. Początkowo wagi wszystkich punktów wynoszą $0$. Little Cyan Fish musi wykonać po kolei $q$ operacji, z których każda ma jedną z poniższych postaci:

• 1 x y z d w: Dla każdego punktu $(X, Y, Z)$ spełniającego $|X - x| < d$, $|Y - y| < d$ oraz $|Z - z| < d$, dodaj $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ do jego wagi.
• 2 x1 x2 y1 y2 z1 z2: Wypisz łączną wagę punktów $(X, Y, Z)$ spełniających $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ oraz $z_1 \le Z \le z_2$. Ponieważ suma może być duża, podaj ją modulo $2^{28}$.

Wejście

Test składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

W każdym przypadku testowym pierwszy wiersz zawiera jedną liczbę całkowitą $q$ ($1 \le q \le 5 \times 10^4$), oznaczającą liczbę operacji.

Każdy z kolejnych $q$ wierszy zawiera liczby całkowite w jednej z poniższych postaci:

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

Gwarantowane jest, że suma $q$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^4$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu po jednej liczbie całkowitej dla każdej operacji typu $2$: wymaganą sumę wag punktów modulo $2^{28}$. Odpowiedzi podaj w kolejności wykonywania operacji.

Przykład

Wejście 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

Wyjście 1

28
2
4
31
0
0

Uwagi

W pierwszym przypadku testowym pierwsza aktualizacja nadaje początkowi układu współrzędnych wagę $2$, a każdemu z pozostałych $26$ punktów w $[-1, 1]^3$ wagę $1$. Druga aktualizacja dodaje $3$ do punktu $(1, 1, 0)$.

W drugim przypadku testowym wszystkie wagi początkowo znów wynoszą $0$.