Känner du till företaget "Just Odd Inventions"? Företagets verksamhet går ut på att skapa "bara udda uppfinningar". Vi kommer att kalla det JOI-företaget kort och gott.

För att utöka sin verksamhet har JOI-företaget beslutat att anställa nya medarbetare.

Det finns $N$ kandidater till tjänsterna. Varje kandidat tilldelas ett nummer från $1$ till $N$, och varje kandidat tilldelas ett heltal som kallas ett utvärderingsvärde.

I denna anställningsprocess kommer alla kandidater vars utvärderingsvärde är minst ett visst värde att anställas. De nyanställda medarbetarna delas in i flera grupper. Grupperna av nyanställda medarbetare bildas så att följande villkor uppfylls:

• När både kandidat $a$ och kandidat $b$ ($a < b$) anställs, hamnar dessa medarbetare i samma grupp om och endast om alla kandidater $c$ ($a \le c \le b$) också anställs.

Som personalansvarig på JOI-företaget ska du uppskatta antalet grupper som bildas i denna anställningsprocess genom att behandla totalt $M$ frågor i ordning. Den $j$-te frågan är av en av följande två typer:

• Hitta antalet grupper som bildas när alla kandidater med ett utvärderingsvärde på minst $B_j$ anställs. Denna typ av fråga kallas en svarsfråga.
• Uppdatera utvärderingsvärdet för kandidat $C_j$ till $D_j$. Denna typ av fråga kallas en uppdateringsfråga.

Uppgift

Givet information om $M$ frågor, skriv ett program som beräknar antalet grupper för varje svarsfråga.

Indata

Läs följande data från standardindata:

• Den första raden innehåller två mellanslagsseparerade heltal $N$ och $M$. Detta anger att det finns $N$ kandidater och att du ska behandla $M$ frågor.
• Den $i$-te raden av de följande $N$ raderna ($1 \le i \le N$) innehåller ett heltal $A_i$. Detta anger att utvärderingsvärdet för kandidat $i$ är $A_i$ innan några frågor har behandlats.
• Den $j$-te raden av de följande $M$ raderna ($1 \le j \le M$) innehåller två eller tre mellanslagsseparerade heltal. Låt det första heltalet vara $T_j$. Innehållet på denna rad är ett av följande:
  1. Om $T_j = 1$ innehåller denna rad heltalen $T_j$ och $B_j$ separerade med ett mellanslag. Detta anger att den $j$-te frågan är en svarsfråga för att hitta antalet grupper som bildas när alla kandidater med ett utvärderingsvärde på minst $B_j$ anställs.
  2. Om $T_j = 2$ innehåller denna rad heltalen $T_j$, $C_j$ och $D_j$ separerade med mellanslag. Detta anger att den $j$-te frågan är en uppdateringsfråga för att uppdatera utvärderingsvärdet för kandidat $C_j$ till $D_j$.

Utdata

Skriv ut antalet grupper för varje svarsfråga till standardutdata, ett per rad.

Begränsningar

All indata uppfyller följande villkor:

• $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 finns minst ett $j$ ($1 \le j \le M$) sådant att $T_j = 1$.

Delproblem

Delproblem 1 [10 poäng]

Följande villkor är uppfyllda: $N \le 2\,000$. $M \le 2\,000$.

Delproblem 2 [30 poäng]

• $T_j = 1$ ($1 \le j \le M$) är uppfyllt.

Delproblem 3 [60 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

2
1
2

Förklaring

1. Den första frågan är en svarsfråga. Om kandidaterna 1, 2 och 4 (som har utvärderingsvärden på minst 5) anställs bildas en grupp bestående av kandidat 1 och kandidat 2, samt en grupp bestående av kandidat 4, så skriv ut 2.
2. Den andra frågan är en uppdateringsfråga. Uppdatera utvärderingsvärdet för kandidat 4 till 1.
3. Den tredje frågan är en svarsfråga. Om kandidaterna 1 och 2 (som har utvärderingsvärden på minst 5) anställs bildas en grupp bestående av kandidat 1 och kandidat 2, så skriv ut 1.
4. Den fjärde frågan är en svarsfråga. Om kandidaterna 1, 2, 3 och 5 (som har utvärderingsvärden på minst 3) anställs bildas en grupp bestående av kandidaterna 1, 2 och 3, samt en grupp bestående av kandidat 5, så skriv ut 2.

Indata 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

Förklaring

Indata 2 uppfyller begränsningarna för Delproblem 2.

Indata 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