ظهرت $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$)، حيث $a_i$ قوة الهجوم و$b_i$ قوة الدفاع للكائن رقم $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$.