喺一個寧靜嘅杜鵑花園入面，出現咗 $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$。