Í friðsælum asaleugarði hafa $n$ hættulegar verur birst. Hver vera býr yfir árásarafli og varnarafli. Upphaflega hefur $i$-ta veran ($1 \le i \le n$) árásaraflið $a_i$ og varnaraflið $b_i$.

Þú, verndari asaleugarðsins, getur ímyndað þér í huganum stríð á milli þeirra. Stríð samanstendur af nokkrum (hugsanlega $0$) bardögum. Í hverjum ímynduðum bardaga velur þú tvær lifandi verur $i$ og $j$ ($1 \le i,j \le n$, $i \ne j$), og:

• Ef árásarafl veru $i$ er stærra en eða jafnt og varnarafl veru $j$ (þ.e. $a_i \ge b_j$), þá getur $i$ sigrað $j$ í bardaganum og $j$ telst úr leik.
• Annars gerist ekkert.

Athugaðu að stríðin eru ímynduð; það er að segja, vera sem er úr leik getur ekki tekið þátt í fleiri bardögum í sama stríði, en hún endurheimtir þrótt sinn í upphafi næsta stríðs og getur því tekið þátt í bardögum í síðari stríðum.

Verurnar eru óstöðugar og taka stökkbreytingum með tímanum. Gefnar eru $q$ stökkbreytingar. Eftir hverja stökkbreytingu breytast eiginleikar einnar veru. Nánar tiltekið, í $i$-tu stökkbreytingunni uppfærist árásarafl $v_i$-tu verunnar í $x_i$ og varnarafl hennar uppfærist í $y_i$. Athugaðu að stökkbreytingarnar eru varanlegar; eftir $i$-tu stökkbreytinguna safnast áhrif fyrstu $i-1$ stökkbreytinganna saman.

Þar sem hver vera sem eftir stendur ógnar blómunum stöðugt vilt þú finna minnsta mögulega fjölda vera sem eftir standa eftir besta mögulega bardagaröð í ímynduðu stríði. Þú þarft að svara spurningunni fyrir öll ástönd fyrir allar stökkbreytingar og eftir hverja stökkbreytingu.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ og $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), þar sem $n$ er fjöldi vera og $q$ er fjöldi stökkbreytinga.

Næstu $n$ línur inntaksins lýsa öllum verunum. $i$-ta línan af þeim inniheldur tvær heiltölur $a_i$ og $b_i$ ($1 \le a_i,b_i \le 10^9$), þar sem $a_i$ er árásaraflið og $b_i$ er varnaraflið hjá $i$-tu verunni.

Næstu $q$ línur inntaksins lýsa öllum stökkbreytingunum. $i$-ta línan af þeim inniheldur þrjár heiltölur $v_i$, $x_i$ og $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), þar sem $x_i$ er nýja árásarafl veru $v_i$ og $y_i$ er nýja varnarafl veru $v_i$.

Úttak

Prentaðu $q+1$ línur, þar sem hver lína inniheldur eina heiltölu, sem eru svörin fyrir allar stökkbreytingar og eftir hverja stökkbreytingu í röð.

Dæmi

Inntak 1

3 1
1 1
2 2
3 3
2 2 4

Úttak 1

1
2

Athugasemd

Í dæminu, áður en stökkbreytingarnar hefjast, getur þriðja veran sigrað fyrstu og aðra veruna. Ljóst er að þetta er besta röð ímyndaðra bardaga, svo svarið er $1$.

Eftir að fyrstu stökkbreytingunni lýkur verður árásarafl annarrar verunnar $2$ og varnarafl hennar verður $4$. Nú getur þriðja veran aðeins sigrað fyrstu veruna, þannig að $2$ verur verða eftir. Hægt er að sanna að engin betri lausn sé til, svo svarið er $2$.