시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB43266.667%

문제

Ü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.

예제 입력 1

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

예제 출력 1

8
3
6
2

Esimese sündmusena ostab mees ülikonnad poodidest 3 ...10.

Teise sündmusena ostab mees ülikonnad poodidest 4, 9 ja 10.

Kolmas sündmus üheski poes hindu ei muuda.

Neljandas sündmuses ostab mees ülikonnad poodidest 2, 3, 4, 5, 9 ja 10.

Viienda sündmuse järel on ülikondade hinnad poodides 10, 10, 10, 7, 6, 5, 5, 5, 3 ja 1.

Kuuendas sündmuses ostab mees ülikonnad poodidest 2 ja 4.