¡La 38.ª Olimpiada Internacional de Estructuras de Datos tendrá lugar pronto! Little Cyan Fish quiere clasificarse, por lo que debe superar el concurso de selección del equipo nacional. Como miembro del equipo Fish, se le ha planteado el siguiente problema en el concurso Fish Team Selection.

En el espacio tridimensional, hay infinitos puntos $(x, y, z)$ con coordenadas enteras. Todos los pesos de los puntos son inicialmente $0$. Little Cyan Fish debe realizar $q$ operaciones en orden, cada una de la forma:

• 1 x y z d w: Para cada punto $(X, Y, Z)$ con $|X - x| < d$, $|Y - y| < d$ y $|Z - z| < d$, sumar $w \cdot (d - \max(|X - x|, |Y - y|, |Z - z|))$ a su peso.
• 2 x1 x2 y1 y2 z1 z2: Imprimir el peso total de los puntos $(X, Y, Z)$ con $x_1 \le X \le x_2$, $y_1 \le Y \le y_2$ y $z_1 \le Z \le z_2$. El total puede ser grande, así que dalo módulo $2^{28}$.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un único entero $q$ ($1 \le q \le 5 \times 10^4$), que indica el número de operaciones.

Cada una de las siguientes $q$ líneas contiene enteros en una de las siguientes formas:

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

Se garantiza que la suma de $q$ en todos los casos de prueba no supera $5 \times 10^4$.

Salida

Para cada caso de prueba, imprime un entero en una línea separada por cada operación de tipo $2$: la suma requerida de los pesos de los puntos módulo $2^{28}$. Da las respuestas en el orden de las operaciones.

Ejemplos

Entrada 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

Salida 1

28
2
4
31
0
0

Nota

En el primer caso de prueba, la primera actualización asigna peso $2$ al origen y peso $1$ a cada uno de los otros $26$ puntos en $[-1, 1]^3$. La segunda actualización suma $3$ al punto $(1, 1, 0)$.

En el segundo caso de prueba, todos los pesos son inicialmente $0$ de nuevo.