Little L possède une grille triangulaire régulière, où chaque ligne de la grille est un segment reliant les $n$ points de division correspondants des côtés adjacents. Ces lignes divisent le triangle équilatéral en plusieurs petits triangles équilatéraux congruents.
Chaque point d'intersection des lignes de la grille sur la figure est représenté par ses coordonnées $(x, y)$. La coordonnée $x$, de haut en bas, varie de $1$ à $n + 1$. $x = 1$ représente le point le plus haut, tandis que $x = n + 1$ représente la ligne du bas. Pour la $i$-ème ligne, les coordonnées $y$ des points de la grille, de gauche à droite, varient de $1$ à $i$.
Dans la grille triangulaire, on considère plusieurs triangles équilatéraux, qui peuvent être orientés vers le haut (droits) ou vers le bas (inversés). Quelle que soit son orientation, un triangle est représenté par trois nombres $x, y, d$. Ici, $(x, y)$ représente les coordonnées du sommet opposé à son côté parallèle à la ligne du bas de la grille, et $d$ représente la longueur de son côté (la longueur du segment).
Par exemple, dans la figure ci-dessous, le triangle équilatéral bleu est un triangle droit avec $(x, y, d) = (4, 2, 3)$. Le triangle équilatéral jaune est un triangle inversé avec $(x, y, d) = (6, 3, 2)$.

Maintenant, un nombre est inscrit sur chaque petit triangle équilatéral unitaire de la grille (un triangle équilatéral de côté $1$, quelle que soit son orientation). Initialement, tous les nombres sur la grille valent $0$. Little L va effectuer les opérations suivantes :
- Choisir un triangle équilatéral et ajouter $w$ à tous les nombres des cases situées à l'intérieur.
- Choisir un triangle équilatéral et demander la somme de tous les nombres des cases situées à l'intérieur.
Il espère que vous pourrez calculer la réponse pour chaque opération de requête. Comme Little L n'aime pas les grands nombres, il vous suffit d'afficher le résultat modulo $2^{32}$.
Entrée
La première ligne de l'entrée contient deux entiers $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Les $q$ lignes suivantes représentent chacune une opération.
Chaque ligne commence par cinq nombres $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$ représente le type d'opération, où $opt = 1$ est une opération de modification et $opt = 2$ est une opération de requête. $type$ indique le type de triangle pour cette opération, où $type = 0$ correspond à un triangle droit et $type = 1$ à un triangle inversé. $x, y, d$ décrivent ce triangle. Si $opt = 1$, il y a un nombre supplémentaire $w$ ($0 \le w < 2^{32}$) qui indique la valeur ajoutée lors de cette opération de modification.
Il est garanti que tous les triangles donnés en entrée ont une aire non nulle et sont des triangles valides entièrement contenus dans le grand triangle.
Sortie
Pour chaque requête avec $opt = 2$, affichez un seul nombre sur une nouvelle ligne, représentant la somme dans la zone modulo $2^{32}$.
Exemples
Entrée 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
Sortie 1
20 11 3
Entrée 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
Sortie 2
0 2 12 0