Den 38:e internationella olympiaden i datastrukturer äger snart rum! Little Cyan Fish vill kvalificera sig, så han måste klara uttagningstävlingen till landslaget. Som medlem i Fish-laget har han fått följande problem i Fish-lagets uttagningstävling.

I det tredimensionella rummet finns det oändligt många punkter $(x, y, z)$ med heltalskoordinater. Alla punktvikter är från början $0$. Little Cyan Fish måste utföra $q$ operationer i ordning, var och en på följande form:

• 1 x y z d w: För varje punkt $(X, Y, Z)$ med $|X - x| < d$, $|Y - y| < d$ och $|Z - z| < d$, addera $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ till dess vikt.
• 2 x1 x2 y1 y2 z1 z2: Skriv ut den totala vikten av punkterna $(X, Y, Z)$ med $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ och $z_1 \le Z \le z_2$. Summan kan vara stor, så ange den modulo $2^{28}$.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $q$ ($1 \le q \le 5 \times 10^4$), som anger antalet operationer.

Var och en av de följande $q$ raderna innehåller heltal på en av följande 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 garanteras att summan av $q$ över alla testfall inte överstiger $5 \times 10^4$.

Utdata

För varje testfall, skriv ut ett heltal på en egen rad för varje operation av typ $2$: den efterfrågade summan av punktvikter modulo $2^{28}$. Ange svaren i samma ordning som operationerna.

Exempel

Indata 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

Förklaring

I det första testfallet ger den första uppdateringen vikten $2$ till origo och vikten $1$ till var och en av de övriga $26$ punkterna i $[-1, 1]^3$. Den andra uppdateringen adderar $3$ till punkten $(1, 1, 0)$.

I det andra testfallet är alla vikter från början $0$ igen.