1. kansainväliset tietorakenteiden olympialaiset järjestetään pian! Little Cyan Fish haluaa päästä mukaan, joten hänen on läpäistävä maajoukkueen karsintakilpailu. Fish-joukkueen jäsenenä hänelle on annettu seuraava tehtävä Fish-joukkueen karsintakilpailussa.

Kolmiulotteisessa avaruudessa on äärettömän monta kokonaislukukoordinaattista pistettä $(x, y, z)$. Kaikkien pisteiden painot ovat aluksi $0$. Little Cyan Fishin on suoritettava järjestyksessä $q$ operaatiota, joista jokainen on jompaakumpaa seuraavista muodoista:

• 1 x y z d w: Jokaiselle pisteelle $(X, Y, Z)$, jolle $|X - x| < d$, $|Y - y| < d$ ja $|Z - z| < d$, lisää sen painoon $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$.
• 2 x1 x2 y1 y2 z1 z2: Tulosta niiden pisteiden $(X, Y, Z)$ kokonaispaino, joille $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ ja $z_1 \le Z \le z_2$. Kokonaispaino voi olla suuri, joten ilmoita se modulo $2^{28}$.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää yhden kokonaisluvun $q$ ($1 \le q \le 5 \times 10^4$), joka ilmoittaa operaatioiden lukumäärän.

Jokainen seuraavista $q$ rivistä sisältää kokonaislukuja jommassakummassa seuraavista muodoista:

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

On taattu, että lukujen $q$ summa yli kaikkien testitapausten on enintään $5 \times 10^4$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi kokonaisluku omalle rivilleen jokaista tyypin $2$ operaatiota kohden: vaadittu pisteiden painojen summa modulo $2^{28}$. Anna vastaukset operaatioiden mukaisessa järjestyksessä.

Esimerkit

Syöte 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

Tuloste 1

28
2
4
31
0
0

Huomautus

Ensimmäisessä testitapauksessa ensimmäinen päivitys antaa origolle painon $2$ ja jokaiselle muulle $26$ pisteelle joukossa $[-1, 1]^3$ painon $1$. Toinen päivitys lisää $3$ pisteeseen $(1, 1, 0)$.

Toisessa testitapauksessa kaikkien pisteiden painot ovat aluksi jälleen $0$.