Czy znasz firmę Just Odd Inventions? Jej działalność polega na tworzeniu „po prostu dziwnych wynalazków”. Będziemy ją tutaj nazywać w skrócie firmą JOI.

Aby rozszerzyć swoją działalność, firma JOI postanowiła zatrudnić nowych pracowników.

Jest $N$ kandydatów na pracowników. Kandydaci są ponumerowani od $1$ do $N$, a każdemu z nich przypisano jedną liczbę całkowitą zwaną oceną.

W ramach tej rekrutacji zostaną zatrudnieni wszyscy kandydaci, których ocena jest nie mniejsza od pewnej wartości. Nowo zatrudnieni pracownicy zostaną podzieleni na grupy. Grupy nowo zatrudnionych pracowników tworzy się tak, aby spełniały następujący warunek:

• Jeśli kandydat $a$ i kandydat $b$ ($a<b$) zostaną zatrudnieni, znajdą się w tej samej grupie wtedy i tylko wtedy, gdy zatrudnieni zostaną wszyscy kandydaci $c$ spełniający $a\le c\le b$.

Jako osoba odpowiedzialna za sprawy kadrowe w firmie JOI masz oszacować liczbę grup utworzonych w tej rekrutacji, przetwarzając kolejno łącznie $M$ zapytań. $j$-te zapytanie jest jednego z dwóch poniższych rodzajów.

• Oblicz liczbę grup, które powstaną, jeśli zatrudnieni zostaną wszyscy kandydaci o ocenie co najmniej $B_j$. Ten rodzaj zapytania nazywamy zapytaniem o wynik.
• Zmień ocenę kandydata $C_j$ na $D_j$. Ten rodzaj zapytania nazywamy zapytaniem aktualizującym.

Zadanie

Mając dane informacje o $M$ zapytaniach, napisz program obliczający liczbę grup dla każdego zapytania o wynik.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczby całkowite $N,M$ oddzielone spacją. Oznacza to, że jest $N$ kandydatów na pracowników i masz przetworzyć $M$ zapytań.
• $i$-ty wiersz ($1\le i\le N$) spośród kolejnych $N$ wierszy zawiera liczbę całkowitą $A_i$. Oznacza to, że przed przetworzeniem zapytań ocena kandydata $i$ wynosi $A_i$.

• $j$-ty wiersz ($1\le j\le M$) spośród kolejnych $M$ wierszy zawiera 2 lub 3 liczby całkowite oddzielone spacjami. Oznaczając pierwszą liczbę przez $T_j$, zawartość wiersza jest jedną z poniższych:

  1. Gdy $T_j=1$, wiersz zawiera liczby całkowite $T_j,B_j$ oddzielone spacją. Oznacza to, że $j$-te zapytanie jest zapytaniem o wynik, w którym należy obliczyć liczbę grup powstałych po zatrudnieniu wszystkich kandydatów o ocenie co najmniej $B_j$.
  2. Gdy $T_j=2$, wiersz zawiera liczby całkowite $T_j,C_j,D_j$ oddzielone spacjami. Oznacza to, że $j$-te zapytanie jest zapytaniem aktualizującym, zmieniającym ocenę kandydata $C_j$ na $D_j$.

Wyjście

Dla każdego zapytania o wynik wypisz na standardowe wyjście liczbę grup, w kolejności zapytań, po jednej w wierszu.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $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$).
• Istnieje co najmniej jedno $j$ ($1\le j\le M$), dla którego $T_j=1$.

Podzadania

Podzadanie 1 [10 punktów]

Spełnione są następujące warunki.

• $N\le 2\,000$.
• $M\le 2\,000$.

Podzadanie 2 [30 punktów]

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

Podzadanie 3 [60 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

2
1
2

Uwagi

1. Pierwsze zapytanie jest zapytaniem o wynik. Gdy zatrudnimy kandydatów $1$, $2$ i $4$, których ocena wynosi co najmniej $5$, powstaną dwie grupy: grupa złożona z kandydatów $1$ i $2$ oraz grupa złożona z kandydata $4$. Wypisujemy więc 2.
2. Drugie zapytanie jest zapytaniem aktualizującym. Zmieniamy ocenę kandydata $4$ na $1$.
3. Trzecie zapytanie jest zapytaniem o wynik. Gdy zatrudnimy kandydatów $1$ i $2$, których ocena wynosi co najmniej $5$, powstanie jedna grupa złożona z kandydatów $1$ i $2$. Wypisujemy więc 1.
4. Czwarte zapytanie jest zapytaniem o wynik. Gdy zatrudnimy kandydatów $1$, $2$, $3$ i $5$, których ocena wynosi co najmniej $3$, powstaną dwie grupy: grupa złożona z kandydatów $1$, $2$ i $3$ oraz grupa złożona z kandydata $5$. Wypisujemy więc 2.

Wejście 2

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

Wyjście 2

0
1
3
3
2

Uwagi

Przykładowe wejście 2 spełnia ograniczenia podzadania 2.

Wejście 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

Wyjście 3

2
1
0