#P18045. Azalea Garden

Azalea Garden

Azalea Garden

有 nn 个生物,第 ii 个生物的攻击力和防御力分别为 ai,bia_i,b_i。

一次战斗选择两个不同的、尚未被消灭的生物 i,ji,j。若 ai≥bja_i\ge b_j,则消灭 jj;否则没有变化。被消灭的生物不能参加本次战争的后续战斗。你可以安排任意有限次战斗,也可以不进行战斗。求最终存活生物数量的最小值。

随后发生 qq 次修改。第 tt 次修改将生物 vtv_t 的攻击力改为 xtx_t,防御力改为 yty_t。修改会保留,后面的修改在当前属性基础上进行。

你需要回答修改前以及每次修改后的最小存活数量。每次回答对应一场独立的假想战争,开始时所有 nn 个生物都存活;此前答案中安排的战斗不会影响下一次回答。

输入格式

第一行两个整数 n,qn,q。

接下来 nn 行,每行两个整数 ai,bia_i,b_i。

接下来 qq 行,每行三个整数 vt,xt,ytv_t,x_t,y_t。

输出格式

输出 q+1q+1 行,依次为修改前、第一次修改后、第二次修改后……的答案。

数据范围

1≤n≤4×1051\le n\le4\times10^5,0≤q≤4×1050\le q\le4\times10^5,1≤vt≤n1\le v_t\le n,所有攻击力和防御力均在 [1,109][1,10^9] 内。

样例 1

输入:

3 1
1 1
2 2
3 3
2 2 4

输出:

1
2