Dans un paisible jardin d’azalées, $n$ créatures dangereuses sont apparues. Chaque créature possède une puissance d’attaque et une puissance de défense. Initialement, la $i$-ième créature ($1 \le i \le n$) a une puissance d’attaque de $a_i$ et une puissance de défense de $b_i$.

En tant que gardien du jardin d’azalées, vous pouvez imaginer mentalement une guerre entre elles. Une guerre consiste en plusieurs batailles (éventuellement $0$). Dans chaque bataille imaginée, vous choisissez deux créatures vivantes $i$ et $j$ ($1 \le i,j \le n$, $i \ne j$), et :

• Si la puissance d’attaque de la créature $i$ est supérieure ou égale à la puissance de défense de la créature $j$ (c’est-à-dire $a_i \ge b_j$), alors $i$ peut vaincre $j$ dans la bataille, et $j$ est considérée comme éliminée.
• Sinon, rien ne se passe.

Les guerres sont imaginaires : une créature éliminée ne peut plus participer aux batailles suivantes de la même guerre, mais elle retrouve sa vigueur au début de la guerre suivante et peut donc participer aux batailles des guerres ultérieures.

Les créatures sont instables et subissent des mutations au fil du temps. On vous donne $q$ mutations. Après chacune, les attributs d’une créature changent. Plus précisément, lors de la $i$-ième mutation, la puissance d’attaque de la $v_i$-ième créature devient $x_i$ et sa puissance de défense devient $y_i$. Les mutations sont persistantes : après la $i$-ième mutation, les effets des $i-1$ premières mutations restent cumulés.

Comme chaque créature restante continue de menacer les fleurs, vous voulez trouver le nombre minimal possible de créatures restantes après une séquence optimale d’une guerre imaginée. Vous devez répondre pour tous les états avant toutes les mutations et après chaque mutation.

Entrée

La première ligne de l’entrée contient deux entiers $n$ et $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), où $n$ est le nombre de créatures et $q$ le nombre de mutations.

Les $n$ lignes suivantes décrivent toutes les créatures. La $i$-ième de ces lignes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i,b_i \le 10^9$), où $a_i$ est la puissance d’attaque et $b_i$ la puissance de défense de la $i$-ième créature.

Les $q$ lignes suivantes décrivent toutes les mutations. La $i$-ième de ces lignes contient trois entiers $v_i$, $x_i$ et $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), où $x_i$ est la nouvelle puissance d’attaque de la créature $v_i$ et $y_i$ la nouvelle puissance de défense de la créature $v_i$.

Sortie

Affichez $q+1$ lignes, chacune contenant un entier : les réponses avant toute mutation, puis après chaque mutation dans l’ordre.

Exemples

Entrée 1

3 1
1 1
2 2
3 3
2 2 4

Sortie 1

1
2

Remarque

Dans l’exemple, avant le début des mutations, la troisième créature peut vaincre la première et la deuxième. C’est manifestement la séquence optimale de batailles imaginées, donc la réponse est $1$.

Après la première mutation, la puissance d’attaque de la deuxième créature devient $2$ et sa puissance de défense devient $4$. La troisième créature ne peut alors vaincre que la première, ce qui laisse $2$ créatures. On peut prouver qu’il n’existe pas de meilleure solution, donc la réponse est $2$.