Little L tiene una cuadrícula triangular regular, donde cada línea de la cuadrícula es un segmento que conecta los correspondientes $n$ puntos de división de los lados adyacentes. Estas líneas dividen el triángulo equilátero en varios triángulos equiláteros más pequeños y congruentes.
Cada punto de intersección de las líneas de la cuadrícula en la figura se representa mediante una coordenada $(x, y)$. La coordenada $x$ de arriba hacia abajo varía de $1$ a $n + 1$. $x = 1$ representa el punto más alto, mientras que $x = n + 1$ representa la línea inferior. Para la $i$-ésima fila, las coordenadas $y$ de los puntos de la cuadrícula de izquierda a derecha varían de $1$ a $i$.
En la cuadrícula triangular hay varios triángulos equiláteros, que pueden estar orientados hacia arriba (normales) o hacia abajo (invertidos). Para cada orientación del triángulo, lo representamos con tres números $x, y, d$. Aquí, $(x, y)$ representa las coordenadas del vértice opuesto a su lado paralelo a la línea inferior de la cuadrícula, y $d$ representa la longitud de su lado (la longitud del segmento).
Por ejemplo, en la siguiente figura, el triángulo equilátero azul es un triángulo orientado hacia arriba, con $(x, y, d) = (4, 2, 3)$. El triángulo equilátero amarillo es un triángulo invertido, con $(x, y, d) = (6, 3, 2)$.

Ahora, en cada celda triangular equilátera unitaria pequeña (un triángulo equilátero de lado $1$, sin importar su orientación), hay un número escrito. Inicialmente, todos los números en las celdas son $0$. Little L realizará las siguientes operaciones:
- Elegir un triángulo equilátero y sumar $w$ a todos los números de las celdas dentro de él.
- Elegir un triángulo equilátero y consultar la suma de todos los números de las celdas dentro de él.
Él espera que puedas calcular la respuesta para cada operación de consulta. Como a Little L no le gustan los números grandes, solo necesitas imprimir el resultado de la respuesta módulo $2^{32}$.
Entrada
La primera línea de la entrada contiene dos enteros $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Las siguientes $q$ líneas representan cada una una operación.
Cada línea comienza con cinco números $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$). $opt$ representa el tipo de operación, donde $opt = 1$ es una operación de modificación y $opt = 2$ es una operación de consulta. $type$ indica el tipo de triángulo para esta operación, donde $type = 0$ es para un triángulo orientado hacia arriba y $type = 1$ es para un triángulo invertido. $x, y, d$ describen este triángulo. Si $opt = 1$, hay un número adicional $w$ ($0 \le w < 2^{32}$) que indica el número sumado durante esta operación de modificación.
Se garantiza que todos los triángulos de entrada tienen un área distinta de cero y son triángulos válidos completamente contenidos dentro del triángulo mayor.
Salida
Para cada consulta con $opt = 2$, imprime un solo número en una nueva línea, que represente la suma dentro del área módulo $2^{32}$.
Ejemplos
Entrada 1
5 5 1 0 3 3 2 2 1 1 6 4 2 3 2 0 1 1 5 2 0 3 2 3 2 1 5 3 2
Salida 1
20 11 3
Entrada 2
10 10 1 0 1 1 5 2 1 1 3 2 1 6 1 1 6 4 2 1 2 0 10 3 1 2 1 5 2 1 2 1 6 4 2 1 0 7 7 1 7 1 1 9 3 1 3 1 0 9 5 2 4 2 0 6 1 2
Salida 2
0 2 12 0