在一个宁静的杜鹃花园中，出现了 $n$ 只危险的生物。每只生物都拥有攻击力和防御力。最初，第 $i$ 只生物（$1 \le i \le n$）的攻击力为 $a_i$，防御力为 $b_i$。

你作为杜鹃花园的守护者，可以在脑海中想象它们之间的一场战争。一场战争由若干次（可能为 $0$ 次）战斗组成。在每次想象的战斗中，你选择两只存活的生物 $i$ 和 $j$（$1 \le i, j \le n$，$i \neq j$），并且：

• 如果生物 $i$ 的攻击力大于或等于生物 $j$ 的防御力（即 $a_i \ge b_j$），那么 $i$ 可以在战斗中击败 $j$，并且 $j$ 被视为被消灭。
• 否则，什么也不会发生。

请注意，战争是想象出来的；也就是说，在同一场战争中被消灭的生物不能用于该场战争后续的战斗，但它会在下一场战争开始时恢复活力，从而可以参与后续战争的战斗。

这些生物是不稳定的，会随着时间的推移发生变异。给你 $q$ 次变异。在每次变异后，某只生物的属性会发生变化。具体来说，在第 $i$ 次变异中，第 $v_i$ 只生物的攻击力更新为 $x_i$，防御力更新为 $y_i$。请注意，变异是持久的；在第 $i$ 次变异之后，前 $i - 1$ 次变异的影响会累积。

由于每只残留的生物都会对花朵构成持续的威胁，你希望找到在想象战争的最佳战斗序列后，剩余生物的最小可能数量。你需要回答在所有变异开始前以及每次变异后的这一问题。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 4 \cdot 10^5$，$0 \le q \le 4 \cdot 10^5$），其中 $n$ 是生物的数量，$q$ 是变异的次数。

接下来的 $n$ 行描述了所有的生物。其中的第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$），其中 $a_i$ 是第 $i$ 只生物的攻击力，$b_i$ 是其防御力。

接下来的 $q$ 行描述了所有的变异。其中的第 $i$ 行包含三个整数 $v_i$，$x_i$ 和 $y_i$（$1 \le v_i \le n$，$1 \le x_i, y_i \le 10^9$），其中 $x_i$ 是生物 $v_i$ 的新攻击力，$y_i$ 是生物 $v_i$ 的新防御力。

输出格式

输出 $q + 1$ 行，每行包含一个整数，依次表示在任何变异发生之前以及每次变异之后的答案。

样例

输入格式 1

3 1
1 1
2 2
3 3
2 2 4

输出格式 1

1
2

说明

在样例中，在变异开始之前，第三只生物可以击败第一只和第二只生物。显然，这是想象战斗的最佳序列，因此答案为 $1$。

在第一次变异结束后，第二只生物的攻击力变为 $2$，防御力变为 $4$。现在第三只生物只能击败第一只生物，剩下 $2$ 只生物。可以证明不存在更好的方案，因此答案为 $2$。