1. alþjóðlega ólympíukeppnin í gagnagrindum fer brátt fram! Little Cyan Fish vill komast áfram, svo hann verður að standast úrtökukeppnina fyrir landsliðið. Sem meðlimur í Fish-liðinu fékk hann eftirfarandi verkefni í úrtökukeppni Fish-liðsins.

Í þrívíðu rúmi eru óendanlega margir punktar $(x, y, z)$ með heiltöluhnit. Allar punktaþyngdir eru í upphafi $0$. Little Cyan Fish þarf að framkvæma $q$ aðgerðir í röð, hverja á öðru hvoru eftirfarandi forma:

• 1 x y z d w: Fyrir hvern punkt $(X, Y, Z)$ með $|X - x| < d$, $|Y - y| < d$ og $|Z - z| < d$, bættu $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ við þyngd hans.
• 2 x1 x2 y1 y2 z1 z2: Skrifaðu út heildarþyngd punktanna $(X, Y, Z)$ með $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ og $z_1 \le Z \le z_2$. Heildarþyngdin getur verið stór, svo gefðu hana upp módúló $2^{28}$.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $q$ ($1 \le q \le 5 \times 10^4$), sem gefur til kynna fjölda aðgerða.

Hver af næstu $q$ línum inniheldur heiltölur á öðru hvoru eftirfarandi forma:

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

Tryggt er að summa $q$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^4$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina heiltölu á sérstaka línu fyrir hverja aðgerð af gerð $2$: umbeðna summu punktaþyngda módúló $2^{28}$. Gefðu svörin í sömu röð og aðgerðirnar.

Dæmi

Inntak 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

Úttak 1

28
2
4
31
0
0

Athugasemd

Í fyrsta prófunartilvikinu gefur fyrsta uppfærslan upphafspunktinum þyngdina $2$ og hverjum hinna $26$ punktanna í $[-1, 1]^3$ þyngdina $1$. Önnur uppfærslan bætir $3$ við punktinn $(1, 1, 0)$.

Í öðru prófunartilvikinu eru allar þyngdir í upphafi $0$ á ný.