Den 38. internasjonale olympiaden i datastrukturer finner snart sted! Little Cyan Fish ønsker å kvalifisere seg, så han må bestå uttakskonkurransen til landslaget. Som medlem av Fish-laget har han fått følgende oppgave i uttakskonkurransen til Fish-laget.

I det tredimensjonale rommet finnes det uendelig mange punkter $(x, y, z)$ med heltallskoordinater. Alle punktvekter er i utgangspunktet $0$. Little Cyan Fish må utføre $q$ operasjoner i rekkefølge, hver på en av følgende former:

• 1 x y z d w: For hvert punkt $(X, Y, Z)$ med $|X - x| < d$, $|Y - y| < d$ og $|Z - z| < d$, legg til $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ til vekten.
• 2 x1 x2 y1 y2 z1 z2: Skriv ut den totale vekten av punktene $(X, Y, Z)$ med $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ og $z_1 \le Z \le z_2$. Summen kan være stor, så oppgi den modulo $2^{28}$.

Inndata

Det er flere testtilfeller. Den første linjen i inndataen inneholder ett enkelt heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen ett enkelt heltall $q$ ($1 \le q \le 5 \times 10^4$), som angir antall operasjoner.

Hver av de neste $q$ linjene inneholder heltall på en av følgende former:

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

Det garanteres at summen av $q$ over alle testtilfeller ikke overstiger $5 \times 10^4$.

Utdata

For hvert testtilfelle skal du skrive ut ett heltall på en egen linje for hver operasjon av type $2$: den etterspurte summen av punktvekter modulo $2^{28}$. Oppgi svarene i samme rekkefølge som operasjonene.

Eksempler

Inndata 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

Utdata 1

28
2
4
31
0
0

Merk

I det første testtilfellet gir den første oppdateringen vekten $2$ til origo og vekten $1$ til hvert av de andre $26$ punktene i $[-1, 1]^3$. Den andre oppdateringen legger til $3$ til punktet $(1, 1, 0)$.

I det andre testtilfellet er alle vekter i utgangspunktet $0$ igjen.