I en fredelig hage med asaleaer har $n$ farlige skapninger dukket opp. Hver skapning har en angrepsstyrke og en forsvarsstyrke. Opprinnelig har den $i$-te skapningen ($1 \le i \le n$) en angrepsstyrke på $a_i$ og en forsvarsstyrke på $b_i$.

Du, vokteren av asaleahagen, kan mentalt forestille deg en krig mellom dem. En krig består av flere (muligens $0$) kamper. I hver forestilte kamp velger du to levende skapninger $i$ og $j$ ($1 \le i,j \le n$, $i \ne j$), og:

• Hvis angrepsstyrken til skapning $i$ er større enn eller lik forsvarsstyrken til skapning $j$ (dvs. $a_i \ge b_j$), kan $i$ beseire $j$ i kampen, og $j$ regnes som eliminert.
• Ellers skjer ingenting.

Merk at krigene er imaginære; det vil si at en eliminert skapning ikke kan brukes i fremtidige kamper i samme krig, men den gjenvinner kreftene sine ved starten av neste krig, og kan dermed delta i kamper i påfølgende kriger.

Skapningene er ustabile og gjennomgår mutasjoner over tid. Du får oppgitt $q$ mutasjoner. Etter hver av mutasjonene endres egenskapene til en skapning. Spesifikt, i den $i$-te mutasjonen får den $v_i$-te skapningen sin angrepsstyrke oppdatert til $x_i$ og sin forsvarsstyrke oppdatert til $y_i$. Merk at mutasjonene er varige; etter den $i$-te mutasjonen er virkningene av de første $i-1$ mutasjonene akkumulert.

Siden hver gjenværende skapning utgjør en vedvarende trussel mot blomstene, ønsker du å finne det minste mulige antallet skapninger som gjenstår etter en optimal sekvens av kamper i en forestilt krig. Du må svare på spørsmålet for alle tilstander før alle mutasjoner og etter hver mutasjon.

Inndata

Den første linjen av inndataene inneholder to heltall $n$ og $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), der $n$ er antallet skapninger og $q$ er antallet mutasjoner.

De neste $n$ linjene av inndataene beskriver alle skapningene. Den $i$-te av disse linjene inneholder to heltall $a_i$ og $b_i$ ($1 \le a_i,b_i \le 10^9$), der $a_i$ er angrepsstyrken og $b_i$ er forsvarsstyrken til den $i$-te skapningen.

De neste $q$ linjene av inndataene beskriver alle mutasjonene. Den $i$-te av disse linjene inneholder tre heltall $v_i$, $x_i$ og $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), der $x_i$ er den nye angrepsstyrken til skapning $v_i$ og $y_i$ er den nye forsvarsstyrken til skapning $v_i$.

Utdata

Skriv ut $q+1$ linjer som hver inneholder et enkelt heltall, som er svarene før noen mutasjoner og etter hver mutasjon i rekkefølge.

Eksempler

Inndata 1

3 1
1 1
2 2
3 3
2 2 4

Utdata 1

1
2

Merk

I eksempelet, før mutasjonene starter, kan den tredje skapningen beseire den første og den andre skapningen. Dette er åpenbart den optimale sekvensen av forestilte kamper, så svaret er $1$.

Etter at den første mutasjonen er ferdig, blir angrepsstyrken til den andre skapningen $2$, og forsvarsstyrken blir $4$. Nå kan den tredje skapningen bare beseire den første skapningen, slik at det gjenstår $2$ skapninger. Det kan bevises at det ikke finnes noen bedre løsning, så svaret er $2$.