La 38ª Olimpiade Internazionale delle Strutture Dati avrà luogo presto! Little Cyan Fish vuole qualificarsi, quindi deve superare la gara di selezione della squadra nazionale. Come membro della squadra Fish, gli è stato assegnato il seguente problema nella gara Fish Team Selection.

Nello spazio tridimensionale, ci sono infiniti punti $(x, y, z)$ a coordinate intere. Tutti i pesi dei punti sono inizialmente $0$. Little Cyan Fish deve eseguire $q$ operazioni in ordine, ciascuna della forma:

• 1 x y z d w: Per ogni punto $(X, Y, Z)$ con $|X - x| < d$, $|Y - y| < d$ e $|Z - z| < d$, aggiungi $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ al suo peso.
• 2 x1 x2 y1 y2 z1 z2: Stampa il peso totale dei punti $(X, Y, Z)$ con $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ e $z_1 \le Z \le z_2$. Il totale può essere grande, quindi fornisci il risultato modulo $2^{28}$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene un singolo intero $q$ ($1 \le q \le 5 \times 10^4$), che indica il numero di operazioni.

Ciascuna delle successive $q$ righe contiene interi in una delle seguenti forme:

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

È garantito che la somma di $q$ su tutti i casi di test non superi $5 \times 10^4$.

Output

Per ogni caso di test, stampa un intero su una riga separata per ogni operazione di tipo $2$: la somma richiesta dei pesi dei punti modulo $2^{28}$. Fornisci le risposte nell'ordine delle operazioni.

Esempi

Input 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

Output 1

28
2
4
31
0
0

Nota

Nel primo caso di test, il primo aggiornamento assegna peso $2$ all'origine e peso $1$ a ciascuno degli altri $26$ punti in $[-1, 1]^3$. Il secondo aggiornamento aggiunge $3$ al punto $(1, 1, 0)$.

Nel secondo caso di test, tutti i pesi sono di nuovo inizialmente $0$.