In einem friedlichen Azaleengarten sind $n$ gefährliche Kreaturen aufgetaucht. Jede Kreatur besitzt eine Angriffsstärke und eine Verteidigungsstärke. Anfangs hat die $i$-te Kreatur ($1 \le i \le n$) die Angriffsstärke $a_i$ und die Verteidigungsstärke $b_i$.

Als Hüter des Azaleengartens kannst du dir einen Krieg zwischen ihnen vorstellen. Ein Krieg besteht aus mehreren Schlachten (möglicherweise $0$). In jeder vorgestellten Schlacht wählst du zwei lebende Kreaturen $i$ und $j$ ($1 \le i,j \le n$, $i \ne j$), und:

• Wenn die Angriffsstärke von Kreatur $i$ mindestens so groß wie die Verteidigungsstärke von Kreatur $j$ ist (also $a_i \ge b_j$), kann $i$ in der Schlacht $j$ besiegen, und $j$ gilt als ausgeschaltet.
• Andernfalls geschieht nichts.

Beachte, dass die Kriege nur vorgestellt sind: Eine ausgeschaltete Kreatur kann an weiteren Schlachten desselben Krieges nicht teilnehmen, erholt sich jedoch zu Beginn des nächsten Krieges und kann daher an Schlachten späterer Kriege teilnehmen.

Die Kreaturen sind instabil und mutieren mit der Zeit. Dir werden $q$ Mutationen gegeben. Nach jeder Mutation ändern sich die Eigenschaften einer Kreatur. Genauer wird bei der $i$-ten Mutation die Angriffsstärke der $v_i$-ten Kreatur auf $x_i$ und ihre Verteidigungsstärke auf $y_i$ gesetzt. Die Mutationen sind dauerhaft: Nach der $i$-ten Mutation bleiben die Auswirkungen der ersten $i-1$ Mutationen angesammelt.

Da jede verbleibende Kreatur die Blumen weiterhin bedroht, möchtest du die kleinstmögliche Anzahl verbleibender Kreaturen nach einer optimalen Abfolge in einem vorgestellten Krieg bestimmen. Beantworte dies für alle Zustände vor sämtlichen Mutationen und nach jeder Mutation.

Eingabe

Die erste Eingabezeile enthält zwei ganze Zahlen $n$ und $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), wobei $n$ die Anzahl der Kreaturen und $q$ die Anzahl der Mutationen ist.

Die nächsten $n$ Zeilen beschreiben alle Kreaturen. Die $i$-te dieser Zeilen enthält zwei ganze Zahlen $a_i$ und $b_i$ ($1 \le a_i,b_i \le 10^9$), wobei $a_i$ die Angriffsstärke und $b_i$ die Verteidigungsstärke der $i$-ten Kreatur ist.

Die nächsten $q$ Zeilen beschreiben alle Mutationen. Die $i$-te dieser Zeilen enthält drei ganze Zahlen $v_i$, $x_i$ und $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), wobei $x_i$ die neue Angriffsstärke von Kreatur $v_i$ und $y_i$ die neue Verteidigungsstärke von Kreatur $v_i$ ist.

Ausgabe

Gib $q+1$ Zeilen mit jeweils einer ganzen Zahl aus: der Reihe nach die Antworten vor jeglichen Mutationen und nach jeder einzelnen Mutation.

Beispiele

Eingabe 1

3 1
1 1
2 2
3 3
2 2 4

Ausgabe 1

1
2

Hinweis

Im Beispiel kann die dritte Kreatur vor Beginn der Mutationen die erste und die zweite besiegen. Offensichtlich ist dies die optimale Abfolge vorgestellter Schlachten, also lautet die Antwort $1$.

Nach der ersten Mutation beträgt die Angriffsstärke der zweiten Kreatur $2$ und ihre Verteidigungsstärke $4$. Nun kann die dritte Kreatur nur die erste besiegen, sodass $2$ Kreaturen übrig bleiben. Es lässt sich beweisen, dass keine bessere Lösung existiert, also lautet die Antwort $2$.