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