Little L ha una griglia triangolare regolare, in cui ogni linea della griglia è un segmento che collega i corrispondenti $n$ punti di suddivisione dei lati adiacenti. Queste linee dividono il triangolo equilatero in diversi triangoli equilateri più piccoli e congruenti.
Ogni punto di intersezione delle linee della griglia nella figura è rappresentato da una coordinata $(x, y)$. La coordinata $x$ dall'alto verso il basso varia da $1$ a $n + 1$. $x = 1$ rappresenta il punto più in alto, mentre $x = n + 1$ rappresenta la linea di base. Per la $i$-esima riga, le coordinate $y$ dei punti della griglia da sinistra a destra variano da $1$ a $i$.
Nella griglia triangolare ci sono diversi triangoli equilateri, che possono essere orientati dritti (con la punta verso l'alto) o capovolti (con la punta verso il basso). Per ciascun orientamento del triangolo, lo rappresentiamo con tre numeri $x, y, d$. Qui $(x, y)$ rappresenta le coordinate del vertice opposto al lato parallelo alla linea di base della griglia, e $d$ rappresenta la lunghezza del suo lato (la lunghezza del segmento).
Ad esempio, nella figura sottostante, il triangolo equilatero blu è un triangolo dritto, con $(x, y, d) = (4, 2, 3)$. Il triangolo equilatero giallo è un triangolo capovolto, con $(x, y, d) = (6, 3, 2)$.

Ora, su ciascuna cella triangolare equilatera unitaria (un triangolo equilatero con lato di lunghezza $1$, indipendentemente dall'orientamento) è scritto un numero. Inizialmente, tutti i numeri sulle celle sono $0$. Little L eseguirà le seguenti operazioni:
- Scegliere un triangolo equilatero e aggiungere $w$ a tutti i numeri sulle celle al suo interno.
- Scegliere un triangolo equilatero e chiedere la somma di tutti i numeri sulle celle al suo interno.
Spera che tu possa calcolare la risposta per ciascuna operazione di query. Poiché a Little L non piacciono i numeri grandi, devi solo stampare il risultato della risposta modulo $2^{32}$.
Input
La prima riga dell'input contiene due interi $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Le successive $q$ righe rappresentano ciascuna un'operazione.
Ogni riga inizia con cinque numeri $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$ rappresenta il tipo di operazione, dove $opt = 1$ è un'operazione di modifica e $opt = 2$ è un'operazione di query. $type$ indica il tipo di triangolo per questa operazione, dove $type = 0$ indica un triangolo dritto e $type = 1$ indica un triangolo capovolto. $x, y, d$ descrivono questo triangolo. Se $opt = 1$, c'è un numero aggiuntivo $w$ ($0 \le w < 2^{32}$) che indica il valore aggiunto durante questa operazione di modifica.
È garantito che tutti i triangoli in input abbiano area non nulla e siano triangoli validi completamente contenuti all'interno del triangolo più grande.
Output
Per ogni query con $opt = 2$, stampa un singolo numero su una nuova riga, che rappresenta la somma all'interno dell'area modulo $2^{32}$.
Esempi
Input 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
Output 1
20 11 3
Input 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
Output 2
0 2 12 0