Connaissez-vous Just Odd Inventions ? L'activité de cette entreprise consiste à créer « simplement des inventions étranges ». Nous l'appellerons ici, en abrégé, l'entreprise JOI.

Pour développer ses activités, l'entreprise JOI a décidé de recruter de nouveaux employés.

Il y a $N$ candidats. Ils sont numérotés de $1$ à $N$, et chaque candidat possède un entier appelé sa note d'évaluation.

Pour ce recrutement, tous les candidats dont la note d'évaluation est supérieure ou égale à un certain seuil seront recrutés. Les nouveaux employés seront répartis en plusieurs groupes. Les groupes des nouveaux employés sont formés de manière à respecter la condition suivante.

• Si les candidats $a$ et $b$ ($a<b$) sont tous deux recrutés, ces employés appartiennent au même groupe si et seulement si tous les candidats $c$ ($a \le c \le b$) sont recrutés.

En tant que responsable des ressources humaines de l'entreprise JOI, vous devez estimer le nombre de groupes formés lors de ce recrutement en traitant dans l'ordre un total de $M$ requêtes. La $j$-ième requête est de l'un des deux types suivants.

• Déterminer le nombre de groupes formés si tous les candidats dont la note d'évaluation est supérieure ou égale à $B_j$ sont recrutés. Nous appelons ce type de requête une requête de réponse.
• Remplacer la note d'évaluation du candidat $C_j$ par $D_j$. Nous appelons ce type de requête une requête de mise à jour.

Tâche

Étant données les informations sur les $M$ requêtes, écrivez un programme qui détermine le nombre de groupes pour chaque requête de réponse.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient les entiers $N,M$, séparés par un espace. Cela signifie qu'il y a $N$ candidats et que vous devez traiter $M$ requêtes.
• La $i$-ième ligne ($1 \le i \le N$) des $N$ lignes suivantes contient un entier $A_i$. Cela signifie qu'avant le traitement des requêtes, la note d'évaluation du candidat $i$ est $A_i$.

• La $j$-ième ligne ($1 \le j \le M$) des $M$ lignes suivantes contient deux ou trois entiers séparés par des espaces. En notant $T_j$ le premier entier, le contenu de cette ligne est l'un des suivants.

• Si $T_j=1$, cette ligne contient les entiers $T_j,B_j$, séparés par un espace. Cela signifie que la $j$-ième requête est une requête de réponse demandant le nombre de groupes formés si tous les candidats dont la note d'évaluation est supérieure ou égale à $B_j$ sont recrutés.

• Si $T_j=2$, cette ligne contient les entiers $T_j,C_j,D_j$, séparés par des espaces. Cela signifie que la $j$-ième requête est une requête de mise à jour remplaçant la note d'évaluation du candidat $C_j$ par $D_j$.

Sortie

Pour chaque requête de réponse, écrivez sur la sortie standard le nombre de groupes, dans l'ordre, à raison d'une réponse par ligne.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $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$).
• Il existe au moins un $j$ ($1 \le j \le M$) tel que $T_j=1$.

Sous-tâches

Sous-tâche 1 [10 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [30 points]

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

Sous-tâche 3 [60 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

2
1
2

Remarque

1. La première requête est une requête de réponse. Si l'on recrute les candidats $1$, $2$ et $4$, dont la note d'évaluation est supérieure ou égale à $5$, deux groupes sont formés : un groupe composé des candidats $1$ et $2$, et un groupe composé du candidat $4$. On écrit donc $2$.
2. La deuxième requête est une requête de mise à jour. La note d'évaluation du candidat $4$ devient $1$.
3. La troisième requête est une requête de réponse. Si l'on recrute les candidats $1$ et $2$, dont la note d'évaluation est supérieure ou égale à $5$, un seul groupe composé des candidats $1$ et $2$ est formé. On écrit donc $1$.
4. La quatrième requête est une requête de réponse. Si l'on recrute les candidats $1$, $2$, $3$ et $5$, dont la note d'évaluation est supérieure ou égale à $3$, deux groupes sont formés : un groupe composé des candidats $1$, $2$ et $3$, et un groupe composé du candidat $5$. On écrit donc $2$.

Entrée 2

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

Sortie 2

0
1
3
3
2

Remarque

L'exemple d'entrée 2 satisfait les contraintes de la sous-tâche 2.

Entrée 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

Sortie 3

2
1
0