I en fridfull trädgård av azaleor har $n$ farliga varelser dykt upp. Varje varelse har en attackstyrka och en försvarsstyrka. Ursprungligen har den $i$-te varelsen ($1 \le i \le n$) en attackstyrka på $a_i$ och en försvarsstyrka på $b_i$.

Du, azaleaträdgårdens väktare, kan i tankarna föreställa dig ett krig mellan dem. Ett krig består av flera (möjligen $0$) strider. I varje föreställd strid väljer du två levande varelser $i$ och $j$ ($1 \le i,j \le n$, $i \ne j$), och:

• Om attackstyrkan hos varelse $i$ är större än eller lika med försvarsstyrkan hos varelse $j$ (dvs. $a_i \ge b_j$), kan $i$ besegra $j$ i striden, och $j$ betraktas som eliminerad.
• Annars händer ingenting.

Observera att krigen är imaginära; det vill säga, en eliminerad varelse kan inte användas i framtida strider i samma krig, men den återfår sin kraft i början av nästa krig och kan därmed delta i strider i efterföljande krig.

Varelserna är föränderliga och genomgår mutationer över tid. Du får $q$ mutationer. Efter var och en av mutationerna ändras attributen hos en varelse. Specifikt, i den $i$-te mutationen får den $v_i$-te varelsen sin attackstyrka uppdaterad till $x_i$ och sin försvarsstyrka uppdaterad till $y_i$. Observera att mutationerna är bestående; efter den $i$-te mutationen ackumuleras effekterna av de första $i-1$ mutationerna.

Eftersom varje kvarvarande varelse utgör ett pågående hot mot blommorna vill du hitta det minsta möjliga antalet varelser som återstår efter en optimal följd av strider i ett föreställt krig. Du måste besvara frågan för alla tillstånd före alla mutationer och efter varje mutation.

Indata

Den första raden i indata innehåller två heltal $n$ och $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), där $n$ är antalet varelser och $q$ är antalet mutationer.

De följande $n$ raderna i indata beskriver alla varelser. Den $i$-te av dessa rader innehåller två heltal $a_i$ och $b_i$ ($1 \le a_i,b_i \le 10^9$), där $a_i$ är attackstyrkan och $b_i$ är försvarsstyrkan hos den $i$-te varelsen.

De följande $q$ raderna i indata beskriver alla mutationer. Den $i$-te av dessa rader innehåller tre heltal $v_i$, $x_i$ och $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), där $x_i$ är den nya attackstyrkan hos varelse $v_i$ och $y_i$ är den nya försvarsstyrkan hos varelse $v_i$.

Utdata

Skriv ut $q+1$ rader som var och en innehåller ett enda heltal, vilket är svaren före några mutationer och efter varje mutation i ordning.

Exempel

Indata 1

3 1
1 1
2 2
3 3
2 2 4

Utdata 1

1
2

Anmärkning

I exemplet, innan mutationerna börjar, kan den tredje varelsen besegra den första och den andra varelsen. Detta är uppenbarligen den optimala följden av föreställda strider, så svaret är $1$.

Efter att den första mutationen är slut blir den andra varelsens attackstyrka $2$ och dess försvarsstyrka blir $4$. Nu kan den tredje varelsen bara besegra den första varelsen, vilket lämnar $2$ varelser kvar. Det kan bevisas att ingen bättre lösning finns, så svaret är $2$.