У тихому саду азалій з’явилося $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$.