Whiteking s'apprête à jouer à un jeu de décoration local. La zone qu'il souhaite décorer se présente sous la forme d'une grille $N \times N$ dans laquelle la grille unitaire est représentée par des tuiles carrées de $1 \times 1$. Les coordonnées de la tuile en haut à gauche sont $(1, 1)$ et les coordonnées de la tuile en bas à droite sont $(N, N)$. Ainsi, les coordonnées d'une tuile font référence aux coordonnées du coin inférieur droit de cette tuile. Il en résulte que la tuile située en $(x, y)$ occupe une zone carrée correspondant à $[x - 1, x] \times [y - 1, y]$. Chaque tuile possède sa propre valeur de beauté ; initialement, toutes les tuiles ont une valeur de beauté de 0.

Le jeu de décoration local est un jeu où le joueur gagne des points en utilisant les trois actions suivantes :

• Diviser la grille en différentes zones en traçant une ligne droite horizontalement ou verticalement. Initialement, il n'y a qu'une seule zone de taille $N \times N$. Les lignes sont infinies dans les deux directions : par exemple, si vous tracez une ligne droite horizontalement et une autre verticalement, la zone initiale sera divisée en un total de quatre zones.
• Sélectionner une tuile et décorer la zone à laquelle elle appartient. En conséquence, la beauté de toutes les tuiles dans la zone décorée est augmentée d'une valeur donnée.
• Sélectionner un rectangle sur la grille et gagner des points égaux à la beauté de la tuile la plus belle qu'il contient.

Whiteking veut savoir à l'avance combien de points il gagnera pour chaque action du troisième type. Il vous montrera donc une liste ordonnée d'actions qu'il va effectuer. Les actions seront données dans le format suivant :

• "1 a b" : Si $a$ est 0, tracez la ligne droite $x = b$, et si $a$ est 1, tracez $y = b$.
• "2 a b X" : Sélectionnez la tuile située en $(a, b)$, décorez la zone à laquelle elle appartient, en augmentant la beauté de toutes les tuiles qu'elle contient de $X$.
• "3 a b c d" : Sélectionnez un rectangle avec $(a, b)$ comme tuile en haut à gauche et $(c, d)$ comme tuile en bas à droite, et gagnez des points égaux à la beauté de la tuile la plus belle qu'il contient.

Aidez Whiteking à déterminer quel sera le score pour chaque action du troisième type.

Entrée

La première ligne contient deux entiers $N$ et $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$).

Chacune des $Q$ lignes suivantes décrit une action dans le format indiqué dans l'énoncé du problème.

Pour une action de type 1, $0 \le a \le 1$ et $1 \le b \le N - 1$.

Pour une action de type 2, $1 \le a, b \le N$ et $-10^9 \le X \le 10^9$.

Pour une action de type 3, $1 \le a \le c \le N$ et $1 \le b \le d \le N$.

Il y a au plus 25 000 actions de type 2, et au moins 1 action de type 3.

Sortie

Pour chaque action du troisième type, affichez le score que Whiteking obtiendra pour cette action.

Exemples

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

Sortie 1

0
-3
-3
1