Деректер құрылымдары бойынша 38-ші Халықаралық олимпиада жақында өтеді! Little Cyan Fish іріктеуден өткісі келеді, сондықтан ол ұлттық құрама командаға іріктеу жарысынан өтуі керек. Fish командасының мүшесі ретінде оған Fish командасына іріктеу жарысында келесі есеп берілді.

Үш өлшемді кеңістікте бүтін координаталары бар шексіз көп $(x, y, z)$ нүктелері бар. Барлық нүктелердің салмақтары бастапқыда $0$-ге тең. Little Cyan Fish ретімен $q$ операцияны орындауы керек, олардың әрқайсысы келесі түрлердің бірінде болады:

• 1 x y z d w: $|X - x| < d$, $|Y - y| < d$ және $|Z - z| < d$ шарттарын қанағаттандыратын әрбір $(X, Y, Z)$ нүктесі үшін оның салмағына $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ мәнін қосыңыз.
• 2 x1 x2 y1 y2 z1 z2: $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ және $z_1 \le Z \le z_2$ шарттарын қанағаттандыратын $(X, Y, Z)$ нүктелерінің жалпы салмағын шығарыңыз. Жалпы салмақ үлкен болуы мүмкін, сондықтан оны $2^{28}$ модулі бойынша беріңіз.

Енгізу

Бірнеше тест жағдайлары бар. Енгізудің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін бірінші жолда операциялар санын білдіретін бір бүтін сан $q$ ($1 \le q \le 5 \times 10^4$) берілген.

Келесі $q$ жолдың әрқайсысында келесі түрлердің біріндегі бүтін сандар берілген:

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

Барлық тест жағдайлары бойынша $q$ мәндерінің қосындысы $5 \times 10^4$-тен аспайтынына кепілдік беріледі.

Шығару

Әрбір тест жағдайы үшін $2$-ші түрдегі әрбір операцияға жеке жолға бір бүтін сан шығарыңыз: нүкте салмақтарының қажетті қосындысын $2^{28}$ модулі бойынша. Жауаптарды операциялардың ретімен беріңіз.

Мысалдар

Енгізу 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

Шығару 1

28
2
4
31
0
0

Ескертпе

Бірінші тест жағдайында бірінші жаңарту координаталар басына $2$ салмағын және $[-1, 1]^3$ ішіндегі басқа $26$ нүктенің әрқайсысына $1$ салмағын береді. Екінші жаңарту $(1, 1, 0)$ нүктесіне $3$ қосады.

Екінші тест жағдайында барлық салмақтар бастапқыда қайтадан $0$-ге тең болады.