בגן אזליאות שליו הופיעו $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$.