Você conhece a empresa Just Odd Inventions? A atividade dessa empresa é fazer «invenções simplesmente estranhas». Aqui, vamos chamá-la de JOI, para abreviar.

A JOI decidiu contratar novos funcionários para expandir os seus negócios.

Há $N$ candidatos a funcionário. Eles são numerados de $1$ a $N$, e a cada candidato é atribuído um número inteiro chamado valor de avaliação.

Nesta contratação, serão contratados todos os candidatos cujo valor de avaliação seja maior ou igual a um determinado valor. Os novos funcionários serão divididos em alguns grupos. Os grupos dos novos funcionários serão formados de modo a satisfazer a seguinte condição:

• Se os candidatos $a$ e $b$ ($a<b$) forem ambos contratados, esses funcionários pertencerão ao mesmo grupo se, e somente se, todos os candidatos $c$ ($a \le c \le b$) forem contratados.

Como responsável pelos recursos humanos da JOI, você deverá estimar a quantidade de grupos que serão formados nesta contratação processando, em ordem, um total de $M$ consultas. A consulta de número $j$ é de um dos dois tipos seguintes:

• Determinar a quantidade de grupos formados caso sejam contratados todos os candidatos com valor de avaliação maior ou igual a $B_j$. Chamaremos uma consulta desse tipo de consulta de resposta.
• Atualizar o valor de avaliação do candidato $C_j$ para $D_j$. Chamaremos uma consulta desse tipo de consulta de atualização.

Tarefa

Dadas as informações sobre as $M$ consultas, escreva um programa que determine a quantidade de grupos correspondente a cada consulta de resposta.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $N$, $M$, separados por um espaço. Isso significa que há $N$ candidatos a funcionário e que você processará $M$ consultas.
• A linha de número $i$ ($1 \le i \le N$) entre as $N$ linhas seguintes contém um inteiro $A_i$. Isso significa que, antes do processamento das consultas, o valor de avaliação do candidato $i$ é $A_i$.

• A linha de número $j$ ($1 \le j \le M$) entre as $M$ linhas seguintes contém 2 ou 3 inteiros separados por espaços. Seja $T_j$ o primeiro inteiro. O conteúdo dessa linha é um dos seguintes:

  1. Se $T_j=1$, a linha contém os inteiros $T_j$, $B_j$, separados por um espaço. Isso significa que a consulta de número $j$ é uma consulta de resposta que pede a quantidade de grupos formados caso sejam contratados todos os candidatos com valor de avaliação maior ou igual a $B_j$.
  2. Se $T_j=2$, a linha contém os inteiros $T_j$, $C_j$, $D_j$, separados por espaços. Isso significa que a consulta de número $j$ é uma consulta de atualização que atualiza o valor de avaliação do candidato $C_j$ para $D_j$.

Saída

Para cada consulta de resposta, escreva na saída padrão a quantidade de grupos, em ordem, uma por linha.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $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$).
• Existe pelo menos um $j$ ($1 \le j \le M$) para o qual $T_j=1$.

Subtarefas

Subtarefa 1 [10 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 2 [30 pontos]

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

Subtarefa 3 [60 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

2
1
2

Explicação

1. A primeira consulta é uma consulta de resposta. Ao contratar os candidatos $1$, $2$ e $4$, cujos valores de avaliação são maiores ou iguais a $5$, formam-se 2 grupos: um com os candidatos $1$ e $2$, e outro com o candidato $4$. Portanto, escreve-se $2$.
2. A segunda consulta é uma consulta de atualização. O valor de avaliação do candidato $4$ é atualizado para $1$.
3. A terceira consulta é uma consulta de resposta. Ao contratar os candidatos $1$ e $2$, cujos valores de avaliação são maiores ou iguais a $5$, forma-se 1 grupo com os candidatos $1$ e $2$. Portanto, escreve-se $1$.
4. A quarta consulta é uma consulta de resposta. Ao contratar os candidatos $1$, $2$, $3$ e $5$, cujos valores de avaliação são maiores ou iguais a $3$, formam-se 2 grupos: um com os candidatos $1$, $2$ e $3$, e outro com o candidato $5$. Portanto, escreve-se $2$.

Entrada 2

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

Saída 2

0
1
3
3
2

Explicação

O exemplo de entrada 2 satisfaz as restrições da subtarefa 2.

Entrada 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

Saída 3

2
1
0