La 38e Olympiade internationale des structures de données aura bientôt lieu ! Little Cyan Fish veut se qualifier, il doit donc réussir le concours de sélection de l'équipe nationale. En tant que membre de l'équipe Fish, il a reçu le problème suivant lors du concours Fish Team Selection.

Dans l'espace tridimensionnel, il existe une infinité de points $(x, y, z)$ à coordonnées entières. Les poids de tous les points valent initialement $0$. Little Cyan Fish doit effectuer $q$ opérations dans l'ordre, chacune sous la forme :

• 1 x y z d w : Pour chaque point $(X, Y, Z)$ tel que $|X - x| < d$, $|Y - y| < d$ et $|Z - z| < d$, ajouter $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ à son poids.
• 2 x1 x2 y1 y2 z1 z2 : Afficher le poids total des points $(X, Y, Z)$ tels que $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ et $z_1 \le Z \le z_2$. Le total pouvant être grand, donnez-le modulo $2^{28}$.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $q$ ($1 \le q \le 5 \times 10^4$), indiquant le nombre d'opérations.

Chacune des $q$ lignes suivantes contient des entiers sous l'une des formes suivantes :

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

Il est garanti que la somme de $q$ sur tous les cas de test ne dépasse pas $5 \times 10^4$.

Sortie

Pour chaque cas de test, affichez un entier sur une ligne séparée pour chaque opération de type $2$ : la somme demandée des poids des points modulo $2^{28}$. Donnez les réponses dans l'ordre des opérations.

Exemples

Entrée 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

Sortie 1

28
2
4
31
0
0

Remarque

Dans le premier cas de test, la première mise à jour attribue un poids de $2$ à l'origine et un poids de $1$ à chacun des $26$ autres points de $[-1, 1]^3$. La seconde mise à jour ajoute $3$ au point $(1, 1, 0)$.

Dans le second cas de test, tous les poids valent à nouveau initialement $0$.