在一座寧靜的杜鵑花園中，出現了 $n$ 隻危險生物。每隻生物都有攻擊力與防禦力。最初，第 $i$ 隻生物（$1 \le i \le n$）的攻擊力為 $a_i$，防禦力為 $b_i$。

身為杜鵑花園的守護者，你可以在腦中想像牠們之間的一場戰爭。一場戰爭由若干場（也可能是 $0$ 場）戰鬥組成。在每場想像的戰鬥中，你選擇兩隻存活的生物 $i$ 和 $j$（$1 \le i,j \le n$，$i \ne j$），並且：

• 若生物 $i$ 的攻擊力大於或等於生物 $j$ 的防禦力（即 $a_i \ge b_j$），則 $i$ 可以在戰鬥中擊敗 $j$，而 $j$ 視為被消滅。
• 否則，什麼事也不會發生。

注意，戰爭是想像出來的；也就是說，被消滅的生物不能再參加同一場戰爭中後續的戰鬥，但會在下一場戰爭開始時恢復活力，因此可以參加之後戰爭中的戰鬥。

這些生物並不穩定，會隨時間發生變異。給定 $q$ 次變異。每次變異後，一隻生物的屬性會改變。具體而言，在第 $i$ 次變異中，第 $v_i$ 隻生物的攻擊力更新為 $x_i$，防禦力更新為 $y_i$。注意，變異的效果會持續存在；第 $i$ 次變異後，前 $i-1$ 次變異的影響仍然保留。

由於每隻剩餘生物都會持續威脅花朵，你想找出在一場想像的戰爭中，採取最佳戰鬥序列後，可能剩餘的最少生物數量。你需要對所有變異之前以及每次變異之後的所有狀態回答這個問題。

輸入格式

輸入第一行包含兩個整數 $n$ 和 $q$（$1 \le n \le 4 \cdot 10^5$，$0 \le q \le 4 \cdot 10^5$），其中 $n$ 是生物數量，$q$ 是變異次數。

接下來 $n$ 行描述所有生物。其中第 $i$ 行包含兩個整數 $a_i$ 和 $b_i$（$1 \le a_i,b_i \le 10^9$），分別表示第 $i$ 隻生物的攻擊力 $a_i$ 與防禦力 $b_i$。

接下來 $q$ 行描述所有變異。其中第 $i$ 行包含三個整數 $v_i$、$x_i$ 和 $y_i$（$1 \le v_i \le n$，$1 \le x_i,y_i \le 10^9$），其中 $x_i$ 是生物 $v_i$ 的新攻擊力，$y_i$ 是生物 $v_i$ 的新防禦力。

輸出格式

輸出 $q+1$ 行，每行包含一個整數，依序為任何變異發生之前以及每次變異之後的答案。

範例

輸入格式 1

3 1
1 1
2 2
3 3
2 2 4

輸出格式 1

1
2

說明

在範例中，變異開始之前，第三隻生物可以擊敗第一隻和第二隻生物。顯然，這是最佳的想像戰鬥序列，因此答案是 $1$。

第一次變異結束後，第二隻生物的攻擊力變為 $2$，防禦力變為 $4$。此時第三隻生物只能擊敗第一隻生物，剩下 $2$ 隻生物。可以證明不存在更好的方案，因此答案是 $2$。