Litli L á reglulegt þríhyrningsnet, þar sem hver netlína er strik sem tengir samsvarandi $n$ skiptipunkta á aðliggjandi hliðum. Þessar netlínur skipta jafnhliða þríhyrningnum í nokkra eins minni jafnhliða þríhyrninga.
Fyrir hvern skurðpunkt netlínanna á myndinni táknum við hann með hnitinu $(x, y)$. $x$-hnitið ofan frá og niður spanna frá $1$ til $n + 1$. $x = 1$ táknar efsta punktinn, en $x = n + 1$ táknar neðstu línuna. Fyrir $i$-tu röðina spanna $y$-hnit netpunktanna frá vinstri til hægri frá $1$ til $i$.
Í þríhyrningsnetinu eru nokkrir jafnhliða þríhyrningar, sem geta snúið rétt (með oddinn upp) eða á hvolfi (með oddinn niður). Fyrir hvora stefnu þríhyrningsins táknum við hann með þremur tölum $x, y, d$. Hér táknar $(x, y)$ hnit hornpunktsins sem er á móti hlið hans sem er samsíða neðstu línu netsins, og $d$ táknar hliðarlengd hans (lengd striksins).
Til dæmis, á myndinni hér að neðan er blái jafnhliða þríhyrningurinn réttur þríhyrningur með $(x, y, d) = (4, 2, 3)$. Guli jafnhliða þríhyrningurinn er þríhyrningur á hvolfi með $(x, y, d) = (6, 3, 2)$.

Nú er tala skrifuð á hvern einingar-smáþríhyrning í netinu (jafnhliða þríhyrning með hliðarlengd $1$, óháð stefnu). Í upphafi eru allar tölur á netinu $0$. Litli L mun framkvæma eftirfarandi aðgerðir:
- Velja jafnhliða þríhyrning og bæta $w$ við allar tölur á reitunum innan hans.
- Velja jafnhliða þríhyrning og spyrja um summu allra talna á reitunum innan hans.
Hann vonar að þú getir reiknað svarið fyrir hverja fyrirspurnaraðgerð. Þar sem Litla L líkar ekki við stórar tölur þarftu aðeins að prenta niðurstöðu svarsins modulo $2^{32}$.
Inntak
Fyrsta línan í inntakinu inniheldur tvær heiltölur $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
Næstu $q$ línur tákna hver um sig eina aðgerð.
Hver lína byrjar á fimm tölum $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$ táknar tegund aðgerðar, þar sem $opt = 1$ er breytingaraðgerð og $opt = 2$ er fyrirspurnaraðgerð. $type$ gefur til kynna tegund þríhyrnings í þessari aðgerð, þar sem $type = 0$ er fyrir réttan þríhyrning og $type = 1$ er fyrir þríhyrning á hvolfi. $x, y, d$ lýsa þessum þríhyrningi. Ef $opt = 1$ er aukatala $w$ ($0 \le w < 2^{32}$) sem gefur til kynna töluna sem bætt er við í þessari breytingaraðgerð.
Tryggt er að allir þríhyrningar í inntaki hafi flatarmál sem er ekki núll og séu gildir þríhyrningar sem eru algjörlega innan stóra þríhyrningsins.
Úttak
Fyrir hverja fyrirspurn með $opt = 2$ skal prenta eina tölu á nýrri línu, sem táknar summuna innan svæðisins modulo $2^{32}$.
Dæmi
Inntak 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
Úttak 1
20 11 3
Inntak 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
Úttak 2
0 2 12 0