Kennst du das Unternehmen Just Odd Inventions? Seine Tätigkeit besteht darin, „einfach nur seltsame Erfindungen“ zu machen. Im Folgenden nennen wir es kurz JOI.

Um sein Geschäft auszubauen, hat JOI beschlossen, neue Mitarbeiter einzustellen.

Es gibt $N$ Bewerber. Sie sind von $1$ bis $N$ nummeriert, und jedem Bewerber ist eine ganze Zahl zugeordnet, die als Bewertungswert bezeichnet wird.

Bei dieser Einstellung werden alle Bewerber eingestellt, deren Bewertungswert mindestens einen bestimmten Wert erreicht. Die neu eingestellten Mitarbeiter werden in mehrere Gruppen eingeteilt. Diese Gruppen werden so gebildet, dass die folgende Bedingung erfüllt ist.

• Wenn sowohl Bewerber $a$ als auch Bewerber $b$ ($a<b$) eingestellt werden, gehören diese Mitarbeiter genau dann derselben Gruppe an, wenn alle Bewerber $c$ mit $a\le c\le b$ eingestellt werden.

Als Personalverantwortlicher von JOI sollst du die Anzahl der bei dieser Einstellung entstehenden Gruppen abschätzen, indem du insgesamt $M$ Anfragen der Reihe nach bearbeitest. Die Anfrage mit Nummer $j$ ist von einer der folgenden beiden Arten.

• Bestimme die Anzahl der Gruppen, die entstehen, wenn alle Bewerber mit einem Bewertungswert von mindestens $B_j$ eingestellt werden. Diese Art von Anfrage nennen wir Ergebnisanfrage.
• Aktualisiere den Bewertungswert von Bewerber $C_j$ auf $D_j$. Diese Art von Anfrage nennen wir Aktualisierungsanfrage.

Aufgabe

Schreibe ein Programm, das anhand der Informationen über $M$ Anfragen für jede Ergebnisanfrage die Anzahl der Gruppen bestimmt.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

• Die erste Zeile enthält die durch ein Leerzeichen getrennten ganzen Zahlen $N,M$. Dies bedeutet, dass es $N$ Bewerber gibt und du $M$ Anfragen bearbeitest.
• Die Zeile mit Nummer $i$ ($1\le i\le N$) unter den nächsten $N$ Zeilen enthält die ganze Zahl $A_i$. Dies bedeutet, dass Bewerber $i$ vor der Bearbeitung der Anfragen den Bewertungswert $A_i$ hat.

• Die Zeile mit Nummer $j$ ($1\le j\le M$) unter den nächsten $M$ Zeilen enthält 2 oder 3 durch Leerzeichen getrennte ganze Zahlen. Bezeichne die erste Zahl mit $T_j$. Der Inhalt dieser Zeile ist einer der folgenden:

  1. Falls $T_j=1$, enthält die Zeile die durch ein Leerzeichen getrennten ganzen Zahlen $T_j,B_j$. Dies bedeutet, dass die Anfrage mit Nummer $j$ eine Ergebnisanfrage ist, die die Anzahl der Gruppen bestimmt, wenn alle Bewerber mit einem Bewertungswert von mindestens $B_j$ eingestellt werden.
  2. Falls $T_j=2$, enthält die Zeile die durch Leerzeichen getrennten ganzen Zahlen $T_j,C_j,D_j$. Dies bedeutet, dass die Anfrage mit Nummer $j$ eine Aktualisierungsanfrage ist, die den Bewertungswert von Bewerber $C_j$ auf $D_j$ aktualisiert.

Ausgabe

Gib für jede Ergebnisanfrage der Reihe nach die Anzahl der Gruppen in einer eigenen Zeile auf der Standardausgabe aus.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).
• Es gibt mindestens ein $j$ ($1\le j\le M$) mit $T_j=1$.

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

Die folgenden Bedingungen sind erfüllt.

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

Teilaufgabe 2 [30 Punkte]

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

Teilaufgabe 3 [60 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

2
1
2

Hinweis

1. Die erste Anfrage ist eine Ergebnisanfrage. Wenn die Bewerber 1, 2 und 4 mit einem Bewertungswert von mindestens $5$ eingestellt werden, entstehen zwei Gruppen: eine aus den Bewerbern 1 und 2 und eine aus Bewerber 4. Daher wird 2 ausgegeben.
2. Die zweite Anfrage ist eine Aktualisierungsanfrage. Der Bewertungswert von Bewerber 4 wird auf $1$ aktualisiert.
3. Die dritte Anfrage ist eine Ergebnisanfrage. Wenn die Bewerber 1 und 2 mit einem Bewertungswert von mindestens $5$ eingestellt werden, entsteht eine Gruppe aus den Bewerbern 1 und 2. Daher wird 1 ausgegeben.
4. Die vierte Anfrage ist eine Ergebnisanfrage. Wenn die Bewerber 1, 2, 3 und 5 mit einem Bewertungswert von mindestens $3$ eingestellt werden, entstehen zwei Gruppen: eine aus den Bewerbern 1, 2 und 3 und eine aus Bewerber 5. Daher wird 2 ausgegeben.

Eingabe 2

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

Ausgabe 2

0
1
3
3
2

Hinweis

Beispiel 2 erfüllt die Beschränkungen von Teilaufgabe 2.

Eingabe 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

Ausgabe 3

2
1
0