静かなツツジの庭に、$n$ 体の危険な生物が現れました。それぞれの生物は攻撃力と防御力を持ちます。最初、$i$ 番目の生物（$1 \le i \le n$）の攻撃力は $a_i$、防御力は $b_i$ です。

ツツジの庭を守るあなたは、生物同士の戦争を頭の中で想像できます。戦争は何回かの戦闘（$0$ 回でもよい）からなります。想像上の各戦闘では、生きている異なる 2 体の生物 $i$ と $j$（$1 \le i,j \le n$、$i \ne j$）を選び、次のようにします。

• 生物 $i$ の攻撃力が生物 $j$ の防御力以上（すなわち $a_i \ge b_j$）なら、$i$ は戦闘で $j$ を倒すことができ、$j$ は排除されたものとみなされます。
• そうでなければ、何も起こりません。

戦争は想像上のものであることに注意してください。つまり、排除された生物は同じ戦争の以後の戦闘には参加できませんが、次の戦争の開始時には元気を取り戻し、その後の戦争の戦闘に参加できます。

生物は不安定で、時間とともに変異します。$q$ 回の変異が与えられます。各変異の後、1 体の生物の属性が変化します。具体的には、$i$ 回目の変異では $v_i$ 番目の生物の攻撃力が $x_i$、防御力が $y_i$ に更新されます。変異の効果は持続することに注意してください。$i$ 回目の変異の後も、それまでの $i-1$ 回の変異の影響は蓄積されています。

残った生物はすべて花に脅威を与え続けるので、想像上の戦争で最適な戦闘列を選んだ後に残る生物の数の最小値を求めたいです。すべての変異の前、および各変異の後のすべての状態について、この問いに答えてください。

入力

入力の最初の行には 2 つの整数 $n$ と $q$（$1 \le n \le 4 \cdot 10^5$、$0 \le q \le 4 \cdot 10^5$）が含まれます。$n$ は生物の数、$q$ は変異の回数です。

続く $n$ 行はすべての生物を記述します。その $i$ 行目には 2 つの整数 $a_i$ と $b_i$（$1 \le a_i,b_i \le 10^9$）が含まれ、$a_i$ は $i$ 番目の生物の攻撃力、$b_i$ はその防御力です。

続く $q$ 行はすべての変異を記述します。その $i$ 行目には 3 つの整数 $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 つ含め、変異が起こる前、および各変異の後の答えを順に出力します。

入出力例

入力 1

3 1
1 1
2 2
3 3
2 2 4

出力 1

1
2

注記

例では、変異が始まる前に、3 番目の生物が 1 番目と 2 番目の生物を倒せます。明らかにこれは最適な想像上の戦闘列なので、答えは $1$ です。

最初の変異の後、2 番目の生物の攻撃力は $2$、防御力は $4$ になります。このとき 3 番目の生物は 1 番目の生物しか倒せず、$2$ 体が残ります。よりよい方法は存在しないと証明できるので、答えは $2$ です。