地牢攻略

柠檬王国的勇者维塔罗想通过攻略地牢来提升等级。

共有 $N$ 个地牢。第 $i$ 个地牢的难度由两个整数 $A_i,B_i$ 表示。当维塔罗当前等级为 $X$ 时，挑战第 $i$ 个地牢会得到如下结果。

• 若 $X \le A_i$，则攻略失败，等级不变。
• 若 $B_i \le X$，则攻略成功，等级增加 $$。

已经尝试过的地牢不能再次尝试。维塔罗可以自由决定挑战地牢的顺序以及挑战的数量。

维塔罗的初始等级为 $L$。对于初始的地牢状态，以及每次修改查询执行后的地牢状态，分别求从等级 $L$ 开始能够达到的最大等级。

计算每一个答案时，维塔罗都重新从等级 $L$ 开始，并且所有地牢都处于尚未尝试的状态。计算某个答案时进行的挑战不会影响其他答案。

每次修改查询由三个整数 $i,a,b$ 给出。执行该查询后，第 $i$ 个地牢的难度变为 $A_i=a$、$B_i=b$。修改后的值会保留到之后的查询中。

输入格式如下：

$N\ Q\ L$ $A_1\ B_1$ $$

输出 $Q+1$ 行。

第一行输出尚未执行任何修改查询时能够达到的最大等级。

对于每个 $1 \le q \le Q$，第 $q+1$ 行输出执行前 次修改查询后能够达到的最大等级。

• $1 \le N \le 500\,000$.
• $0 \le Q \le 200\,000$.
• $1\le L\le {}^{}$.