29951번 - Marslaste õunaaed 다국어

문제

Zaqquat peab Marsil õunaaeda, kus kasvab $N$ õunapuud. Puud on pikas sirges reas ja nummerdatud 1ドル \ldots N$.

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

• Aasta alguses on puu number $i$ õunte küpsus $Z_i$.
• Mingitel hetkedel aasta jooksul küpsevad kõik õunad küpsusega $X$ ühe astme võrra, saades uueks küpsuseks $X + 1$.

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

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

입력

Faili esimesel real on õunapuude arv $N$ (1ドル \le N \le 500,000円$) ja sündmuste arv $Q$ (1ドル \le Q \le 500,000円$).

Faili teisel real on $N$ tühikutega eraldatud täisarvu $Z_i$ (1ドル \le Z_i \le 1,000円,000円$): õunte küpsused aasta algul.

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

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

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.

제한

힌트