Bombončići

문제

Priprema Hrvatske informatičke olimpijade za djevojke zahtijeva puno truda, pa tako i puno odmora. Kako bi bila što efikasnija u svojim odmorima, Iva je već prošloga tjedna pripremila stol na kojem je poredano $nn$ hrpa bombončića: na $ii$-toj hrpi stavila je $a_{i}a\_i$ bombončića.

Ali Iva nije jedina koja voli bombončiće, voli ih i Maja! Maja bi često zapitala Ivu: "Možemo li podijeliti bombončiće od $l_{i}l\_i$-te do $r_{i}r\_i$-te hrpe?"

Na što bi joj Iva odgovorila: "Možemo podijeliti one hrpe na kojima je broj bombončića paran tako da svaka dobije polovicu bombončića s te hrpe. No, one hrpe na kojima je broj bombončića neparan, ne možemo podijeliti na jednak način. Što ćemo s njima?"

Maja je odmah pojela sve bombončiće koje su odmah mogle podijeliti, a nakon toga je započela cjelodnevna rasprava oko toga kako podijeliti neparne hrpe. Na kraju dana, kada su obje zaspale, njihova mama je potajno zamijenila sve hrpe oko kojih se nisu mogle dogovoriti tako da je na svakoj takvoj hrpi sada točno $x_{i}x\_i$ bombončića.

Kako je priprema Hrvatske informatičke olimpijade za djevojke zahtjevnija nego što je očekivala, Iva nikad nije našla vremena za jesti bombončiće. Ali često bi pogledavala na stol i razmišljala koliko bi bombončića pojela kad bi pojela sve bombončiće od $l_{j}l\_j$-te do $r_{j}r\_j$-te hrpe. Pomozite joj odgovoriti na ta pitanja!

입력

U prvom retku su prirodni brojevi $nn$ i $qq$ (1 ≤ n ≤ 10^5 i 1 ≤ q ≤ 10^5), broj hrpa bombončića i broj događaja.

U drugom retku je n prirodnih brojeva $a_{i}a\_i$ (1 ≤ a_i ≤ 2^{25}), broj bombončića na $ii$-toj hrpi.

Slijedi $qq$ redaka koji opisuju događaje.

Prvi broj u retku opisa događaja je prirodan broj $tt$ (1 ≤ t ≤ 2), tip događaja.

• Za $t=1t\; =\; 1$ u istom retku slijede prirodni brojevi $l_{i}l\_i$, $r_{i}r\_i$, $x_{i}x\_i$ (1 ≤ l_i ≤ r_i ≤ n i 1 ≤ x ≤ 2^{25}), koji označavaju da je Maja pitala Ivu da podijele bombončiće od $l_{i}l\_i$-te do $r_{i}r\_i$-te hrpe, a $x_{i}x\_i$ je broj bombončića na koji je njihova mama promijenila hrpe nakon što su zaspale.
• Za $t=2t\; =\; 2$ u istom retku slijede prirodni brojevi $l_{i}l\_i$, $r_{i}r\_i$ (1 ≤ l_i ≤ r_i ≤ n), koji označavaju da se Iva upitala koliko ukupno ima bombončića od $l_{i}l\_i$-te do $r_{i}r\_i$-te hrpe.

출력

Na svaki događaj tipa $22$ u zaseban red odgovorite Ivi na njeno pitanje.

힌트

Pojašnjenje prvog probnog primjera: Ilustracija prikazuje kako se mijenjao broj bombončića na stolu nakon svake promjene.

[이미지 1]