Num tranquilo jardim de azáleas, apareceram $n$ criaturas perigosas. Cada criatura possui um poder de ataque e um poder de defesa. Inicialmente, a $i$-ésima criatura ($1 \le i \le n$) tem poder de ataque $a_i$ e poder de defesa $b_i$.

Tu, guardião do jardim de azáleas, podes imaginar mentalmente uma guerra entre elas. Uma guerra consiste em várias batalhas (possivelmente $0$). Em cada batalha imaginada, escolhes duas criaturas vivas $i$ e $j$ ($1 \le i,j \le n$, $i \ne j$), e:

• Se o poder de ataque da criatura $i$ for maior ou igual ao poder de defesa da criatura $j$ (isto é, $a_i \ge b_j$), então $i$ pode derrotar $j$ na batalha, e $j$ é considerada eliminada.
• Caso contrário, nada acontece.

Nota que as guerras são imaginárias: uma criatura eliminada não pode participar nas batalhas seguintes da mesma guerra, mas recupera o vigor no início da próxima guerra, podendo participar nas batalhas das guerras posteriores.

As criaturas são instáveis e sofrem mutações ao longo do tempo. São dadas $q$ mutações. Após cada uma, os atributos de uma criatura mudam. Especificamente, na $i$-ésima mutação, a $v_i$-ésima criatura tem o poder de ataque atualizado para $x_i$ e o poder de defesa para $y_i$. As mutações são persistentes: após a $i$-ésima mutação, os efeitos das primeiras $i-1$ mutações permanecem acumulados.

Como cada criatura restante continua a ameaçar as flores, queres encontrar o menor número possível de criaturas restantes após uma sequência ótima de uma guerra imaginada. Deves responder para todos os estados antes de todas as mutações e depois de cada mutação.

Entrada

A primeira linha da entrada contém dois inteiros $n$ e $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), onde $n$ é o número de criaturas e $q$ o número de mutações.

As $n$ linhas seguintes descrevem todas as criaturas. A $i$-ésima dessas linhas contém dois inteiros $a_i$ e $b_i$ ($1 \le a_i,b_i \le 10^9$), onde $a_i$ é o poder de ataque e $b_i$ o poder de defesa da $i$-ésima criatura.

As $q$ linhas seguintes descrevem todas as mutações. A $i$-ésima dessas linhas contém três inteiros $v_i$, $x_i$ e $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), onde $x_i$ é o novo poder de ataque da criatura $v_i$ e $y_i$ o novo poder de defesa da criatura $v_i$.

Saída

Imprime $q+1$ linhas, cada uma com um único inteiro: as respostas antes de qualquer mutação e depois de cada mutação, por ordem.

Exemplos

Entrada 1

3 1
1 1
2 2
3 3
2 2 4

Saída 1

1
2

Nota

No exemplo, antes de começarem as mutações, a terceira criatura pode derrotar a primeira e a segunda. Claramente, esta é a sequência ótima de batalhas imaginadas, pelo que a resposta é $1$.

Após a primeira mutação, o poder de ataque da segunda criatura passa a $2$ e o seu poder de defesa a $4$. Agora, a terceira criatura só pode derrotar a primeira, restando $2$ criaturas. Pode provar-se que não existe solução melhor, pelo que a resposta é $2$.