Poed

문제

Ühel tänaval on $NN$ rõivapoodi, mis on nummerdatud $1\dots N1\; \backslash ldots\; N$. Kõik poed müüvad ülikondi ja poes number $ii$ on ülikonna alghind $A_{i}A\_i$. Seejuures on tänava alguses kallimad poed ja tänavat mööda edasi liikudes on igas järgmises poes ülikonna hind kas eelmisega sama või sellest väiksem.

Seejärel hakkab toimuma kahte tüüpi sündmusi:

1. Poed $1,2,\dots ,X1,\; 2,\; \backslash ldots,\; X$ tulevad välja uute kollektsioonidega ja võivad hindu tõsta; täpsemalt asendatakse iga $1\le i\le X1\; \backslash le\; i\; \backslash le\; X$ korral $A_i:=\max (A_i,Y)A\_i\; :=\; \backslash max(A\_i,\; Y)$.
2. Edev mees käib poodides $X,X+1,\dots ,NX,\; X+1,\; \backslash ldots,\; N$. Poeskäiku alustades on tal $YY$ raha. Kui tal on poodi $ii$ sisendes alles vähemalt $A_{i}A\_i$ raha, siis ostab ta sealt ühe ülikonna ja tema rahavaru kahaneb $A_{i}A\_i$ võrra.

Kirjutada programm, mis leiab iga 2. tüüpi sündmuse kohta, mitu ülikonda mees kokku ostab.

입력

Esimesel real on poodide arv $NN$ ($1\le N\le {10}^{5}1\; \backslash le\; N\; \backslash le\; 10^5$) ja sündmuste arv $QQ$ ($1\le Q\le {10}^{5}1\; \backslash le\; Q\; \backslash le\; 10^5$).

Teisel real on $NN$ täisarvu $A_{i}A\_i$ ($1\le A_i\le {10}^{9}1\; \backslash le\; A\_i\; \backslash le\; 10^9$). On teada, et $A_1\ge A_2\ge \cdots \ge A_{N}A\_1\; \backslash ge\; A\_2\; \backslash ge\; \backslash cdots\; \backslash ge\; A\_N$.

Järgmisel $QQ$ real on igaühel kolm täisarvu: sündmuse tüüp $TT$ ($1\le T\le 21\; \backslash le\; T\; \backslash le\; 2$) ning selle parameetrid $XX$ ja $YY$ ($1\le X\le N1\; \backslash le\; X\; \backslash le\; N$, $1\le Y\le {10}^{9}1\; \backslash le\; Y\; \backslash le\; 10^9$). On teada, et vähemalt üks sündmus on 2. tüüpi.

출력

Väljastada üks rida iga 2. tüüpi sündmuse kohta; igale reale väljastada ostetud ülikondade arv.

10 6
10 10 10 6 6 5 5 5 3 1
2 3 50
2 4 10
1 3 10
2 2 36
1 4 7
2 2 17

8
3
6
2