Di sebuah taman azalea yang tenang, muncul $n$ makhluk berbahaya. Setiap makhluk memiliki kekuatan serang dan kekuatan bertahan. Awalnya, makhluk ke-$i$ ($1 \le i \le n$) memiliki kekuatan serang $a_i$ dan kekuatan bertahan $b_i$.

Anda, penjaga taman azalea, dapat membayangkan perang di antara mereka. Sebuah perang terdiri atas beberapa pertempuran (mungkin $0$). Dalam setiap pertempuran imajiner, Anda memilih dua makhluk yang masih hidup, $i$ dan $j$ ($1 \le i,j \le n$, $i \ne j$), dan:

• Jika kekuatan serang makhluk $i$ lebih besar atau sama dengan kekuatan bertahan makhluk $j$ (yaitu $a_i \ge b_j$), maka $i$ dapat mengalahkan $j$ dalam pertempuran, dan $j$ dianggap tersingkir.
• Jika tidak, tidak terjadi apa-apa.

Perhatikan bahwa perang-perang ini bersifat imajiner; makhluk yang tersingkir tidak dapat mengikuti pertempuran selanjutnya dalam perang yang sama, tetapi pulih pada awal perang berikutnya sehingga dapat mengikuti pertempuran dalam perang-perang selanjutnya.

Makhluk-makhluk itu tidak stabil dan mengalami mutasi seiring waktu. Diberikan $q$ mutasi. Setelah setiap mutasi, atribut satu makhluk berubah. Secara khusus, pada mutasi ke-$i$, kekuatan serang makhluk ke-$v_i$ diperbarui menjadi $x_i$ dan kekuatan bertahannya menjadi $y_i$. Mutasi bersifat menetap: setelah mutasi ke-$i$, dampak $i-1$ mutasi pertama tetap terakumulasi.

Karena setiap makhluk yang tersisa terus mengancam bunga-bunga, Anda ingin mencari jumlah makhluk tersisa paling sedikit setelah urutan optimal dalam sebuah perang imajiner. Jawablah untuk semua keadaan sebelum seluruh mutasi dan setelah setiap mutasi.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ dan $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), dengan $n$ merupakan jumlah makhluk dan $q$ jumlah mutasi.

$n$ baris berikutnya mendeskripsikan semua makhluk. Baris ke-$i$ di antaranya berisi dua bilangan bulat $a_i$ dan $b_i$ ($1 \le a_i,b_i \le 10^9$), dengan $a_i$ merupakan kekuatan serang dan $b_i$ kekuatan bertahan makhluk ke-$i$.

$q$ baris berikutnya mendeskripsikan semua mutasi. Baris ke-$i$ di antaranya berisi tiga bilangan bulat $v_i$, $x_i$, dan $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), dengan $x_i$ merupakan kekuatan serang baru makhluk $v_i$ dan $y_i$ kekuatan bertahan baru makhluk $v_i$.

Keluaran

Keluarkan $q+1$ baris, masing-masing berisi satu bilangan bulat, yaitu jawaban sebelum mutasi apa pun dan setelah setiap mutasi secara berurutan.

Contoh

Masukan 1

3 1
1 1
2 2
3 3
2 2 4

Keluaran 1

1
2

Catatan

Pada contoh, sebelum mutasi dimulai, makhluk ketiga dapat mengalahkan makhluk pertama dan kedua. Jelas ini merupakan urutan pertempuran imajiner yang optimal, sehingga jawabannya adalah $1$.

Setelah mutasi pertama, kekuatan serang makhluk kedua menjadi $2$ dan kekuatan bertahannya menjadi $4$. Kini makhluk ketiga hanya dapat mengalahkan makhluk pertama, sehingga tersisa $2$ makhluk. Dapat dibuktikan bahwa tidak ada solusi lebih baik, sehingga jawabannya adalah $2$.