Marslaste õunaaed

문제

Zaqquat peab Marsil õunaaeda, kus kasvab $NN$ õunapuud. Puud on pikas sirges reas ja nummerdatud $1\dots N1\; \backslash ldots\; N$.

Marsi õunad küpsevad järgmiste reeglite kohaselt:

• Aasta alguses on puu number $ii$ õunte küpsus $Z_{i}Z\_i$.
• Mingitel hetkedel aasta jooksul küpsevad kõik õunad küpsusega $XX$ ühe astme võrra, saades uueks küpsuseks $X+1X\; +\; 1$.

Aeg-ajalt tahab Zaqquat teada, kui palju on õunapuude $LL$ kuni $RR$ hulgas selliseid, mille õunte küpsus ei ületa $YY$.

Kirjutada programm, mis modelleerib õunte küpsemist ja vastab Zaqquati päringutele.

입력

Faili esimesel real on õunapuude arv $NN$ ($1\le N\le 5000001\; \backslash le\; N\; \backslash le\; 500\backslash ,000$) ja sündmuste arv $QQ$ ($1\le Q\le 5000001\; \backslash le\; Q\; \backslash le\; 500\backslash ,000$).

Faili teisel real on $NN$ tühikutega eraldatud täisarvu $Z_{i}Z\_i$ ($1\le Z_i\le 10000001\; \backslash le\; Z\_i\; \backslash le\; 1\backslash ,000\backslash ,000$): õunte küpsused aasta algul.

Järgmisel $QQ$ real on igaühel ühe sündmuse kirjeldus. Rea alguses on sündmuse tüüp $TT$:

• Kui $T=1T\; =\; 1$, on real lisaks veel täisarv $XX$ ($1\le X\le 15000001\; \backslash le\; X\; \backslash le\; 1\backslash ,500\backslash ,000$), mis näitab, et õunad küpsusega $XX$ saavad uueks küpsuseks $X+1X\; +\; 1$.
• Kui $T=2T\; =\; 2$, on real lisaks veel kolm täisarvu $LL$, $RR$ ja $YY$ ($1\le L\le R\le N1\; \backslash le\; L\; \backslash le\; R\; \backslash le\; N$, $1\le Y\le 15000001\; \backslash le\; Y\; \backslash le\; 1\backslash ,500\backslash ,000$), mis näitavad, et Zaqquat tahab teada, kui palju on õunapuude $LL$ kuni $RR$ (mõlemad kaasa arvatud) hulgas selliseid, millel olevate õunte küpsus on maksimaalselt $YY$.

Sündmused on failis nende toimumise kronoloogilises järjekorras.

출력

Faili väljastada iga teist tüüpi sündmuse kohta vastus Zaqquati küsimusele. Vastused väljastada igaüks eraldi reale küsimuste kronoloogilises järjekorras.

7 9
4 1 2 1 4 4 7
2 1 4 1
1 1
2 1 3 1
1 1
1 2
2 3 5 3
2 3 5 2
1 4
2 2 6 4

2
0
2
0
3