Whiteking va a jugar a un juego de decoración local. El área que desea decorar tiene la forma de una cuadrícula de $N \times N$ en la que la cuadrícula unitaria está representada por baldosas cuadradas de $1 \times 1$, las coordenadas de la baldosa superior izquierda son $(1, 1)$ y las coordenadas de la baldosa inferior derecha son $(N, N)$. Por lo tanto, las coordenadas de la baldosa se refieren a las coordenadas de la esquina inferior derecha de la misma. A partir de esto, se puede ver que la baldosa ubicada en $(x, y)$ ocupa un área cuadrada correspondiente a $[x - 1, x] \times [y - 1, y]$. Cada baldosa tiene su propio valor de belleza; inicialmente, todas las baldosas tienen un valor de belleza de 0.

El juego de decoración local es un juego donde el jugador gana puntos utilizando las siguientes tres acciones:

• Dividir la cuadrícula en diferentes zonas trazando una línea recta horizontal o vertical. Inicialmente, solo hay un área de tamaño $N \times N$. Las líneas son infinitas en ambas direcciones: por ejemplo, si trazas una línea recta horizontal y otra vertical, el área inicial se dividirá en un total de cuatro áreas.
• Seleccionar una baldosa y decorar el área a la que pertenece. Como resultado, la belleza de todas las baldosas en el área decorada aumenta en un valor dado.
• Seleccionar un rectángulo en la cuadrícula y ganar puntos iguales a la belleza de la baldosa más bella dentro de él.

Whiteking quiere saber de antemano cuántos puntos ganará por cada acción del tercer tipo. Por lo tanto, te mostrará una lista ordenada de acciones que va a realizar. Las acciones se darán en el siguiente formato:

• “1 a b”: Si $a$ es 0, traza la línea recta $x = b$, y si $a$ es 1, traza la línea recta $y = b$.
• “2 a b X”: Selecciona la baldosa ubicada en $(a, b)$, decora el área a la que pertenece e incrementa la belleza de todas las baldosas en ella en $X$.
• “3 a b c d”: Selecciona un rectángulo con $(a, b)$ como la baldosa superior izquierda y $(c, d)$ como la baldosa inferior derecha, y gana puntos iguales a la belleza de la baldosa más bella dentro de él.

Ayuda a Whiteking a encontrar cuál será la puntuación para cada acción del tercer tipo.

Entrada

La primera línea contiene dos enteros $N$ y $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$).

Cada una de las siguientes $Q$ líneas describe una acción en el formato mostrado en la descripción del problema.

Para una acción de tipo 1, $0 \le a \le 1$ y $1 \le b \le N - 1$.

Para una acción de tipo 2, $1 \le a, b \le N$ y $-10^9 \le X \le 10^9$.

Para una acción de tipo 3, $1 \le a \le c \le N$ y $1 \le b \le d \le N$.

Hay como máximo 25 000 acciones de tipo 2, y al menos 1 acción de tipo 3.

Salida

Para cada acción del tercer tipo, imprime la puntuación que Whiteking obtendrá por esa acción.

Ejemplos

Entrada 1

3 7
3 1 1 3 3
2 1 3 -3
3 1 1 3 3
1 0 1
2 1 1 4
3 2 2 3 3
3 1 1 3 3

Salida 1

0
-3
-3
1