Rauhalliseen atsaleapuutarhaan on ilmestynyt $n$ vaarallista olentoa. Jokaisella olennolla on hyökkäysvoima ja puolustusvoima. Aluksi $i$:nnellä olennolla ($1 \le i \le n$) on hyökkäysvoima $a_i$ ja puolustusvoima $b_i$.

Sinä, atsaleapuutarhan vartija, voit mielessäsi kuvitella sodan niiden välillä. Sota koostuu useasta (mahdollisesti $0$) taistelusta. Jokaisessa kuvitellussa taistelussa valitset kaksi elossa olevaa olentoa $i$ ja $j$ ($1 \le i,j \le n$, $i \ne j$), ja:

• Jos olennon $i$ hyökkäysvoima on suurempi tai yhtä suuri kuin olennon $j$ puolustusvoima (eli $a_i \ge b_j$), niin $i$ voi voittaa olennon $j$ taistelussa, ja $j$ katsotaan eliminoiduksi.
• Muussa tapauksessa mitään ei tapahdu.

Huomaa, että sodat ovat kuvitteellisia; toisin sanoen eliminoitua olentoa ei voida käyttää tulevissa taisteluissa samassa sodassa, mutta se saa voimansa takaisin seuraavan sodan alussa ja voi siten osallistua seuraavien sotien taisteluihin.

Olennot ovat epävakaita ja kokevat mutaatioita ajan myötä. Sinulle annetaan $q$ mutaatiota. Jokaisen mutaation jälkeen yhden olennon ominaisuudet muuttuvat. Tarkemmin sanottuna $i$:nnessä mutaatiossa $v_i$:nnen olennon hyökkäysvoimaksi päivitetään $x_i$ ja puolustusvoimaksi $y_i$. Huomaa, että mutaatiot ovat pysyviä; $i$:nnen mutaation jälkeen ensimmäisen $i-1$ mutaation vaikutukset ovat kertyneet.

Koska jokainen jäljelle jäävä olento on jatkuva uhka kukille, haluat löytää pienimmän mahdollisen määrän olentoja, jotka jäävät jäljelle kuvitellun sodan optimaalisen taistelusarjan jälkeen. Sinun tulee vastata kysymykseen kaikissa tiloissa ennen kaikkia mutaatioita ja jokaisen mutaation jälkeen.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), missä $n$ on olentojen lukumäärä ja $q$ on mutaatioiden lukumäärä.

Seuraavat $n$ syötteen riviä kuvaavat kaikki olennot. Näistä $i$:s rivi sisältää kaksi kokonaislukua $a_i$ ja $b_i$ ($1 \le a_i,b_i \le 10^9$), missä $a_i$ on $i$:nnen olennon hyökkäysvoima ja $b_i$ on sen puolustusvoima.

Seuraavat $q$ syötteen riviä kuvaavat kaikki mutaatiot. Näistä $i$:s rivi sisältää kolme kokonaislukua $v_i$, $x_i$ ja $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), missä $x_i$ on olennon $v_i$ uusi hyökkäysvoima ja $y_i$ on olennon $v_i$ uusi puolustusvoima.

Tuloste

Tulosta $q+1$ riviä, joista jokainen sisältää yhden kokonaisluvun: vastaukset ennen mutaatioita ja jokaisen mutaation jälkeen järjestyksessä.

Esimerkit

Syöte 1

3 1
1 1
2 2
3 3
2 2 4

Tuloste 1

1
2

Huomautus

Esimerkissä ennen mutaatioiden alkua kolmas olento voi voittaa ensimmäisen ja toisen olennon. Selvästikin tämä on optimaalinen kuviteltujen taisteluiden sarja, joten vastaus on $1$.

Ensimmäisen mutaation päätyttyä toisen olennon hyökkäysvoimaksi tulee $2$ ja sen puolustusvoimaksi tulee $4$. Nyt kolmas olento voi voittaa vain ensimmäisen olennon, jolloin jäljelle jää $2$ olentoa. Voidaan todistaa, ettei parempaa ratkaisua ole olemassa, joten vastaus on $2$.