In un sereno giardino di azalee sono apparse $n$ creature pericolose. Ogni creatura possiede una potenza d'attacco e una potenza di difesa. Inizialmente, l'$i$-esima creatura ($1 \le i \le n$) ha una potenza d'attacco pari ad $a_i$ e una potenza di difesa pari a $b_i$.

Tu, il guardiano del giardino di azalee, puoi immaginare mentalmente una guerra tra loro. Una guerra consiste in diverse (possibilmente $0$) battaglie. In ogni battaglia immaginata, scegli due creature vive $i$ e $j$ ($1 \le i,j \le n$, $i \ne j$), e:

• Se la potenza d'attacco della creatura $i$ è maggiore o uguale alla potenza di difesa della creatura $j$ (cioè $a_i \ge b_j$), allora $i$ può sconfiggere $j$ nella battaglia, e $j$ viene considerata eliminata.
• Altrimenti non accade nulla.

Nota che le guerre sono immaginarie; vale a dire, una creatura eliminata non può essere utilizzata per battaglie future nella stessa guerra, ma riacquista il suo vigore all'inizio della guerra successiva e può quindi partecipare alle battaglie delle guerre seguenti.

Le creature sono instabili e subiscono mutazioni nel tempo. Ti vengono date $q$ mutazioni. Dopo ciascuna delle mutazioni, gli attributi di una creatura cambiano. Nello specifico, nell'$i$-esima mutazione, la $v_i$-esima creatura vede la sua potenza d'attacco aggiornata a $x_i$ e la sua potenza di difesa aggiornata a $y_i$. Nota che le mutazioni sono persistenti: dopo l'$i$-esima mutazione, gli effetti delle prime $i-1$ mutazioni rimangono accumulati.

Poiché ogni creatura rimanente rappresenta una minaccia continua per i fiori, vuoi trovare il minimo numero possibile di creature che rimangono dopo una sequenza ottimale di una guerra immaginata. Devi rispondere alla domanda per tutti gli stati: prima di tutte le mutazioni e dopo ciascuna mutazione.

Input

La prima riga dell'input contiene due interi $n$ e $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), dove $n$ è il numero di creature e $q$ è il numero di mutazioni.

Le successive $n$ righe dell'input descrivono tutte le creature. L'$i$-esima di queste righe contiene due interi $a_i$ e $b_i$ ($1 \le a_i,b_i \le 10^9$), dove $a_i$ è la potenza d'attacco e $b_i$ è la potenza di difesa dell'$i$-esima creatura.

Le successive $q$ righe dell'input descrivono tutte le mutazioni. L'$i$-esima di queste righe contiene tre interi $v_i$, $x_i$ e $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), dove $x_i$ è la nuova potenza d'attacco della creatura $v_i$ e $y_i$ è la nuova potenza di difesa della creatura $v_i$.

Output

Stampa $q+1$ righe, ciascuna contenente un singolo intero: le risposte prima di qualsiasi mutazione e dopo ciascuna mutazione in sequenza.

Esempi

Input 1

3 1
1 1
2 2
3 3
2 2 4

Output 1

1
2

Nota

Nell'esempio, prima che inizino le mutazioni, la terza creatura può sconfiggere la prima e la seconda creatura. Chiaramente questa è la sequenza ottimale di battaglie immaginate, quindi la risposta è $1$.

Dopo la fine della prima mutazione, la potenza d'attacco della seconda creatura diventa $2$ e la sua potenza di difesa diventa $4$. Ora la terza creatura può sconfiggere solo la prima creatura, lasciando $2$ creature rimanenti. Si può dimostrare che non esiste una soluzione migliore, quindi la risposta è $2$.