En un tranquilo jardín de azaleas han aparecido $n$ criaturas peligrosas. Cada criatura posee un poder de ataque y un poder de defensa. Inicialmente, la criatura $i$ ($1 \le i \le n$) tiene poder de ataque $a_i$ y poder de defensa $b_i$.

Tú, guardián del jardín de azaleas, puedes imaginar mentalmente una guerra entre ellas. Una guerra consta de varias batallas (posiblemente $0$). En cada batalla imaginada, eliges dos criaturas vivas $i$ y $j$ ($1 \le i,j \le n$, $i \ne j$), y:

• Si el poder de ataque de la criatura $i$ es mayor o igual que el poder de defensa de la criatura $j$ (es decir, $a_i \ge b_j$), entonces $i$ puede derrotar a $j$ en la batalla, y $j$ se considera eliminada.
• En caso contrario, no ocurre nada.

Ten en cuenta que las guerras son imaginarias: una criatura eliminada no puede participar en las batallas posteriores de la misma guerra, pero recupera su vigor al comienzo de la siguiente guerra y puede participar en las batallas de guerras posteriores.

Las criaturas son inestables y sufren mutaciones con el tiempo. Se te dan $q$ mutaciones. Después de cada una, cambian los atributos de una criatura. Concretamente, en la mutación $i$, el poder de ataque de la criatura $v_i$ se actualiza a $x_i$ y su poder de defensa a $y_i$. Las mutaciones son persistentes: después de la mutación $i$, se acumulan los efectos de las primeras $i-1$ mutaciones.

Como cada criatura restante sigue siendo una amenaza para las flores, quieres encontrar el mínimo número posible de criaturas que quedan tras una secuencia óptima de una guerra imaginada. Debes responder para todos los estados antes de todas las mutaciones y después de cada mutación.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), donde $n$ es el número de criaturas y $q$ el número de mutaciones.

Las siguientes $n$ líneas describen todas las criaturas. La línea $i$ de ellas contiene dos enteros $a_i$ y $b_i$ ($1 \le a_i,b_i \le 10^9$), donde $a_i$ es el poder de ataque y $b_i$ el poder de defensa de la criatura $i$.

Las siguientes $q$ líneas describen todas las mutaciones. La línea $i$ de ellas contiene tres enteros $v_i$, $x_i$ e $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), donde $x_i$ es el nuevo poder de ataque de la criatura $v_i$ e $y_i$ el nuevo poder de defensa de la criatura $v_i$.

Salida

Imprime $q+1$ líneas, cada una con un entero: las respuestas antes de cualquier mutación y después de cada mutación, en orden.

Ejemplos

Entrada 1

3 1
1 1
2 2
3 3
2 2 4

Salida 1

1
2

Nota

En el ejemplo, antes de que comiencen las mutaciones, la tercera criatura puede derrotar a la primera y a la segunda. Claramente, esta es la secuencia óptima de batallas imaginadas, por lo que la respuesta es $1$.

Tras la primera mutación, el poder de ataque de la segunda criatura pasa a ser $2$ y su poder de defensa $4$. Ahora la tercera criatura solo puede derrotar a la primera, por lo que quedan $2$ criaturas. Se puede demostrar que no existe una solución mejor, así que la respuesta es $2$.