Little L har ett regelbundet triangelrutnät, där varje rutnätslinje är ett linjesegment som förbinder motsvarande $n$ delningspunkter på intilliggande sidor. Dessa rutnätslinjer delar in den liksidiga triangeln i flera kongruenta mindre liksidiga trianglar.
För varje skärningspunkt mellan rutnätslinjerna i figuren representerar vi den med en koordinat $(x, y)$. $x$-koordinaten uppifrån och ned går från $1$ till $n + 1$. $x = 1$ representerar den översta punkten, medan $x = n + 1$ representerar den nedersta linjen. För den $i$-te raden går rutnätspunkternas $y$-koordinater från vänster till höger från $1$ till $i$.
I triangelrutnätet finns det flera liksidiga trianglar, som kan vara rättvända (med spetsen uppåt) eller inverterade (med spetsen nedåt). För varje orientering av triangeln representerar vi den med tre tal $x, y, d$. Här representerar $(x, y)$ koordinaterna för det hörn som står mittemot sidan som är parallell med rutnätets baslinje, och $d$ representerar dess sidlängd (längden på segmentet).
Till exempel, i figuren nedan är den blå liksidiga triangeln en rättvänd triangel med $(x, y, d) = (4, 2, 3)$. Den gula liksidiga triangeln är en inverterad triangel med $(x, y, d) = (6, 3, 2)$.

Nu står det ett tal skrivet i varje liten enhetstriangel i rutnätet (en liksidig triangel med sidlängden $1$, oavsett orientering). Från början är alla tal i rutnätet $0$. Little L kommer att utföra följande operationer:
- Välj en liksidig triangel och addera $w$ till alla tal i rutnätsfälten inuti den.
- Välj en liksidig triangel och fråga efter summan av alla tal i rutnätsfälten inuti den.
Han hoppas att du kan beräkna svaret för varje frågeoperation. Eftersom Little L inte tycker om stora tal behöver du bara skriva ut resultatet av svaret modulo $2^{32}$.
Indata
Den första raden i indatan innehåller två heltal $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
De följande $q$ raderna representerar var och en en operation.
Varje rad börjar med fem tal $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$ representerar typen av operation, där $opt = 1$ är en ändringsoperation och $opt = 2$ är en frågeoperation. $type$ anger typen av triangel för denna operation, där $type = 0$ står för en rättvänd triangel och $type = 1$ står för en inverterad triangel. $x, y, d$ beskriver denna triangel. Om $opt = 1$ finns det ytterligare ett tal $w$ ($0 \le w < 2^{32}$) som anger det tal som adderas under denna ändringsoperation.
Det garanteras att alla trianglar i indatan har en area skild från noll och är giltiga trianglar som är helt inneslutna i den större triangeln.
Utdata
För varje fråga med $opt = 2$, skriv ut ett enda tal på en ny rad, som representerar summan inom området modulo $2^{32}$.
Exempel
Indata 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
Indata 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