Poed

Ühel tänaval on $N$ rõivapoodi, mis on nummerdatud $1 \ldots N$. Kõik poed müüvad ülikondi ja poes number $i$ on ülikonna alghind $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, \ldots, X$ tulevad välja uute kollektsioonidega ja võivad hindu tõsta; täpsemalt asendatakse iga $1 \le i \le X$ korral $A_i := \max(A_i, Y)$.
2. Edev mees käib poodides $X, X+1, \ldots, N$. Poeskäiku alustades on tal $Y$ raha. Kui tal on poodi $i$ sisendes alles vähemalt $A_i$ raha, siis ostab ta sealt ühe ülikonna ja tema rahavaru kahaneb $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 $N$ ($1 \le N \le 10^5$) ja sündmuste arv $Q$ ($1 \le Q \le 10^5$).

Teisel real on $N$ täisarvu $A_i$ ($1 \le A_i \le 10^9$). On teada, et $A_1 \ge A_2 \ge \cdots \ge A_N$.

Järgmisel $Q$ real on igaühel kolm täisarvu: sündmuse tüüp $T$ ($1 \le T \le 2$) ning selle parameetrid $X$ ja $Y$ ($1 \le X \le N$, $1 \le Y \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.