Pikku L:llä on säännöllinen kolmioruudukko, jossa jokainen ruudukkoviiva on jana, joka yhdistää vierekkäisten sivujen vastaavat $n$ jakopistettä. Nämä ruudukkoviivat jakavat tasasivuisen kolmion useiksi yhteneviksi pienemmiksi tasasivuisiksi kolmioiksi.
Esitämme kuvan ruudukkoviivojen jokaisen leikkauspisteen koordinaatilla $(x, y)$. $x$-koordinaatti ylhäältä alas vaihtelee välillä $1$ – $n + 1$. $x = 1$ tarkoittaa ylintä pistettä, kun taas $x = n + 1$ tarkoittaa alinta viivaa. Rivillä $i$ ruudukkopisteiden $y$-koordinaatit vasemmalta oikealle vaihtelevat välillä $1$ – $i$.
Kolmioruudukossa on useita tasasivuisia kolmioita, jotka voivat olla oikeinpäin (kärki ylöspäin) tai ylösalaisin (kärki alaspäin). Esitämme kummankin suuntaisen kolmion kolmella luvulla $x, y, d$. Tässä $(x, y)$ tarkoittaa sen kärjen koordinaatteja, joka on vastapäätä ruudukon alareunan suuntaista sivua, ja $d$ tarkoittaa sen sivun pituutta (janan pituutta).
Esimerkiksi alla olevassa kuvassa sininen tasasivuinen kolmio on oikeinpäin oleva kolmio, jolle $(x, y, d) = (4, 2, 3)$. Keltainen tasasivuinen kolmio on ylösalaisin oleva kolmio, jolle $(x, y, d) = (6, 3, 2)$.

Nyt jokaiseen pieneen yksikkökolmioruutuun (tasasivuinen kolmio, jonka sivun pituus on $1$ suunnasta riippumatta) on kirjoitettu luku. Aluksi kaikki ruudukon luvut ovat $0$. Pikku L suorittaa seuraavia operaatioita:
- Valitse tasasivuinen kolmio ja lisää $w$ kaikkiin sen sisällä olevien ruutujen lukuihin.
- Valitse tasasivuinen kolmio ja kysy kaikkien sen sisällä olevien ruutujen lukujen summaa.
Hän toivoo, että voit laskea vastauksen jokaiseen kyselyoperaatioon. Koska Pikku L ei pidä suurista luvuista, sinun tarvitsee vain tulostaa vastauksen tulos modulo $2^{32}$.
Syöte
Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Seuraavat $q$ riviä kuvaavat kukin yhden operaation.
Jokainen rivi alkaa viidellä luvulla $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$ ilmaisee operaation tyypin, missä $opt = 1$ on muutosoperaatio ja $opt = 2$ on kyselyoperaatio. $type$ ilmaisee kolmion tyypin tässä operaatiossa, missä $type = 0$ tarkoittaa oikeinpäin olevaa kolmiota ja $type = 1$ ylösalaisin olevaa kolmiota. $x, y, d$ kuvaavat tämän kolmion. Jos $opt = 1$, rivillä on lisäksi luku $w$ ($0 \le w < 2^{32}$), joka ilmaisee tässä muutosoperaatiossa lisättävän luvun.
On taattu, että kaikkien syötteen kolmioiden pinta-ala on nollasta poikkeava ja että ne ovat kelvollisia kolmioita, jotka sisältyvät kokonaan suuremman kolmion sisään.
Tuloste
Tulosta jokaiselle kyselylle, jossa $opt = 2$, omalle rivilleen yksi luku, joka ilmaisee alueen sisällä olevien lukujen summan modulo $2^{32}$.
Esimerkit
Syöte 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
Tuloste 1
20 11 3
Syöte 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
Tuloste 2
0 2 12 0