Kjenner du til selskapet «Just Odd Inventions»? Virksomheten til dette selskapet går ut på å lage «bare rare oppfinnelser». Vi vil kalle det JOI-selskapet for korthets skyld.

For å utvide virksomheten sin har JOI-selskapet bestemt seg for å ansette nye medarbeidere.

Det er $N$ kandidater til stillingene. Hver kandidat får tildelt et nummer fra $1$ til $N$, og hver kandidat får tildelt et heltall som kalles en evalueringsverdi.

I denne ansettelsesprosessen vil alle kandidater hvis evalueringsverdi er minst en viss verdi bli ansatt. De nyansatte medarbeiderne deles inn i flere grupper. Gruppene av nyansatte medarbeidere dannes slik at de oppfyller følgende betingelse:

• Når både kandidat $a$ og kandidat $b$ ($a < b$) blir ansatt, er disse medarbeiderne i samme gruppe hvis og bare hvis alle kandidater $c$ ($a \le c \le b$) også blir ansatt.

Som personalansvarlig i JOI-selskapet skal du estimere antallet grupper som dannes i denne ansettelsesprosessen ved å behandle totalt $M$ spørringer i rekkefølge. Den $j$-te spørringen er en av følgende to typer:

• Finn antallet grupper som dannes når alle kandidater med en evalueringsverdi på minst $B_j$ blir ansatt. Denne typen spørring kalles en svarspørring.
• Oppdater evalueringsverdien til kandidat $C_j$ til $D_j$. Denne typen spørring kalles en oppdateringsspørring.

Oppgave

Gitt informasjon om $M$ spørringer, skriv et program som beregner antallet grupper for hver svarspørring.

Inndata

Les følgende data fra standard inndata:

• Den første linjen inneholder to mellomromseparerte heltall $N$ og $M$. Dette indikerer at det er $N$ kandidater og at du skal behandle $M$ spørringer.
• Den $i$-te linjen av de påfølgende $N$ linjene ($1 \le i \le N$) inneholder et heltall $A_i$. Dette indikerer at før noen spørringer behandles, er evalueringsverdien til kandidat $i$ lik $A_i$.
• Den $j$-te linjen av de påfølgende $M$ linjene ($1 \le j \le M$) inneholder to eller tre mellomromseparerte heltall. La det første heltallet være $T_j$. Innholdet på denne linjen er ett av følgende:
  1. Hvis $T_j = 1$, inneholder denne linjen heltallene $T_j$ og $B_j$ atskilt med et mellomrom. Dette indikerer at den $j$-te spørringen er en svarspørring for å finne antallet grupper som dannes når alle kandidater med en evalueringsverdi på minst $B_j$ blir ansatt.
  2. Hvis $T_j = 2$, inneholder denne linjen heltallene $T_j$, $C_j$ og $D_j$ atskilt med mellomrom. Dette indikerer at den $j$-te spørringen er en oppdateringsspørring for å oppdatere evalueringsverdien til kandidat $C_j$ til $D_j$.

Utdata

Skriv ut antallet grupper for hver svarspørring til standard utdata, ett per linje.

Begrensninger

Alle inndata oppfyller følgende betingelser:

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 2$ ($1 \le j \le M$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $1 \le C_j \le N$ ($1 \le j \le M$).
• $1 \le D_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• Det finnes minst én $j$ ($1 \le j \le M$) slik at $T_j = 1$.

Deloppgaver

Deloppgave 1 [10 poeng]

Følgende betingelser er oppfylt: $N \le 2\,000$. $M \le 2\,000$.

Deloppgave 2 [30 poeng]

• $T_j = 1$ ($1 \le j \le M$) er oppfylt.

Deloppgave 3 [60 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

Utdata 1

2
1
2

Merk

1. Den første spørringen er en svarspørring. Hvis kandidatene 1, 2 og 4 (som har evalueringsverdier på minst 5) blir ansatt, dannes en gruppe bestående av kandidat 1 og kandidat 2, samt en gruppe bestående av kandidat 4, så skriv ut 2.
2. Den andre spørringen er en oppdateringsspørring. Oppdater evalueringsverdien til kandidat 4 til 1.
3. Den tredje spørringen er en svarspørring. Hvis kandidatene 1 og 2 (som har evalueringsverdier på minst 5) blir ansatt, dannes én gruppe bestående av kandidat 1 og kandidat 2, så skriv ut 1.
4. Den fjerde spørringen er en svarspørring. Hvis kandidatene 1, 2, 3 og 5 (som har evalueringsverdier på minst 3) blir ansatt, dannes en gruppe bestående av kandidatene 1, 2 og 3, samt en gruppe bestående av kandidat 5, så skriv ut 2.

Inndata 2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

Utdata 2

0
1
3
3
2

Merk

Inndata 2 oppfyller begrensningene i Deloppgave 2.

Inndata 3

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

Utdata 3

2
1
0