Little L har et reguljært trekantrutenett, der hver rutenettlinje er et linjestykke som forbinder de tilsvarende $n$ delingspunktene på tilstøtende sider. Disse rutenettlinjene deler den likesidede trekanten inn i flere kongruente mindre likesidede trekanter.
Hvert skjæringspunkt mellom rutenettlinjene i figuren representerer vi med en koordinat $(x, y)$. $x$-koordinaten ovenfra og ned går fra $1$ til $n + 1$. $x = 1$ representerer det øverste punktet, mens $x = n + 1$ representerer bunnlinjen. For den $i$-te raden går $y$-koordinatene til rutenettpunktene fra venstre mot høyre fra $1$ til $i$.
I trekantrutenettet er det flere likesidede trekanter, som kan være orientert rettvendt (med spissen opp) eller opp-ned (med spissen ned). For hver orientering av trekanten representerer vi den med tre tall $x, y, d$. Her representerer $(x, y)$ koordinatene til hjørnet som ligger rett overfor siden som er parallell med rutenettets bunnlinje, og $d$ representerer sidelengden (lengden på linjestykket).
For eksempel, i figuren nedenfor er den blå likesidede trekanten en rettvendt trekant med $(x, y, d) = (4, 2, 3)$. Den gule likesidede trekanten er en opp-ned-trekant med $(x, y, d) = (6, 3, 2)$.

Nå er det skrevet et tall på hver liten enhetstrekant i rutenettet (en likesidet trekant med sidelengde $1$, uansett orientering). Til å begynne med er alle tallene i rutenettet $0$. Little L vil utføre følgende operasjoner:
- Velg en likesidet trekant og legg til $w$ på alle tallene i rutenettfeltene inni den.
- Velg en likesidet trekant og spør etter summen av alle tallene i rutenettfeltene inni den.
Han håper du kan beregne svaret for hver spørreoperasjon. Siden Little L ikke liker store tall, trenger du bare å skrive ut resultatet av svaret modulo $2^{32}$.
Inndata
Den første linjen i inndataene inneholder to heltall $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
De neste $q$ linjene representerer hver en operasjon.
Hver linje starter med fem tall $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$ representerer typen operasjon, der $opt = 1$ er en endringsoperasjon og $opt = 2$ er en spørreoperasjon. $type$ angir typen trekant for denne operasjonen, der $type = 0$ er for en rettvendt trekant og $type = 1$ er for en opp-ned-trekant. $x, y, d$ beskriver denne trekanten. Hvis $opt = 1$, følger det et ekstra tall $w$ ($0 \le w < 2^{32}$) som angir tallet som legges til under denne endringsoperasjonen.
Det er garantert at alle trekantene i inndataene har et areal ulikt null og er gyldige trekanter som er fullstendig inneholdt i den store trekanten.
Utdata
For hver spørring med $opt = 2$ skal du skrive ut et enkelt tall på en ny linje, som representerer summen innenfor området modulo $2^{32}$.
Eksempler
Inndata 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
Utdata 1
20 11 3
Inndata 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
Utdata 2
0 2 12 0