Conosci l'azienda "Just Odd Inventions"? L'attività di questa azienda consiste nel creare "invenzioni semplicemente bizzarre". La chiameremo in breve azienda JOI.

Per espandere la propria attività, l'azienda JOI ha deciso di assumere nuovi dipendenti.

Ci sono $N$ candidati per il posto di dipendente. A ciascun candidato è assegnato un numero da $1$ a $N$, e a ciascun candidato è assegnato un intero chiamato valore di valutazione.

In questo processo di assunzione, verranno assunti tutti i candidati il cui valore di valutazione è almeno pari a un certo valore. I dipendenti appena assunti vengono divisi in diversi gruppi. I gruppi di dipendenti appena assunti sono formati in modo da soddisfare la seguente condizione:

• Quando sia il candidato $a$ sia il candidato $b$ ($a < b$) vengono assunti, questi dipendenti si trovano nello stesso gruppo se e solo se anche tutti i candidati $c$ ($a \le c \le b$) vengono assunti.

In qualità di responsabile delle risorse umane presso l'azienda JOI, devi stimare il numero di gruppi formati in questo processo di assunzione elaborando in ordine un totale di $M$ query. La $j$-esima query è di uno dei seguenti due tipi:

• Trova il numero di gruppi formati quando vengono assunti tutti i candidati con un valore di valutazione di almeno $B_j$. Questo tipo di query è chiamato query di risposta.
• Aggiorna il valore di valutazione del candidato $C_j$ a $D_j$. Questo tipo di query è chiamato query di aggiornamento.

Compito

Date le informazioni su $M$ query, scrivi un programma che calcoli il numero di gruppi per ciascuna query di risposta.

Dati di ingresso

Leggi i seguenti dati dallo standard input:

• La prima riga contiene due interi separati da spazio $N$ e $M$. Questo indica che ci sono $N$ candidati e che elaborerai $M$ query.
• La $i$-esima riga delle successive $N$ righe ($1 \le i \le N$) contiene un intero $A_i$. Questo indica che prima di elaborare qualsiasi query, il valore di valutazione del candidato $i$ è $A_i$.
• La $j$-esima riga delle successive $M$ righe ($1 \le j \le M$) contiene due o tre interi separati da spazio. Sia $T_j$ il primo intero. Il contenuto di questa riga è uno dei seguenti:
  1. Se $T_j = 1$, questa riga contiene gli interi $T_j$ e $B_j$ separati da uno spazio. Questo indica che la $j$-esima query è una query di risposta per trovare il numero di gruppi formati quando vengono assunti tutti i candidati con un valore di valutazione di almeno $B_j$.
  2. Se $T_j = 2$, questa riga contiene gli interi $T_j$, $C_j$ e $D_j$ separati da uno spazio. Questo indica che la $j$-esima query è una query di aggiornamento per aggiornare il valore di valutazione del candidato $C_j$ a $D_j$.

Dati di uscita

Stampa sullo standard output il numero di gruppi per ciascuna query di risposta, uno per riga.

Assunzioni

Tutti i dati di input soddisfano le seguenti condizioni:

• $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$).
• Esiste almeno un indice $j$ ($1 \le j \le M$) tale che $T_j = 1$.

Subtask

Subtask 1 [10 punti]

Sono soddisfatte le seguenti condizioni: $N \le 2\,000$. $M \le 2\,000$.

Subtask 2 [30 punti]

• È soddisfatta la condizione $T_j = 1$ ($1 \le j \le M$).

Subtask 3 [60 punti]

Non ci sono limitazioni aggiuntive.

Esempi di input/output

Esempio di input 1

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

Esempio di uscita 1

2
1
2

Note

1. La prima query è una query di risposta. Se vengono assunti i candidati 1, 2 e 4 (che hanno valori di valutazione di almeno 5), si formano un gruppo composto dal candidato 1 e dal candidato 2, e un gruppo composto dal candidato 4, quindi stampa 2.
2. La seconda query è una query di aggiornamento. Aggiorna il valore di valutazione del candidato 4 a 1.
3. La terza query è una query di risposta. Se vengono assunti i candidati 1 e 2 (che hanno valori di valutazione di almeno 5), si forma un unico gruppo composto dal candidato 1 e dal candidato 2, quindi stampa 1.
4. La quarta query è una query di risposta. Se vengono assunti i candidati 1, 2, 3 e 5 (che hanno valori di valutazione di almeno 3), si formano un gruppo composto dai candidati 1, 2 e 3, e un gruppo composto dal candidato 5, quindi stampa 2.

Esempio di input 2

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

Esempio di uscita 2

0
1
3
3
2

Note

L'esempio di input 2 soddisfa i vincoli del Subtask 2.

Esempio di input 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

Esempio di uscita 3

2
1
0