ダンジョン攻略

レモン王国の勇者ビタロは、ダンジョンを攻略してレベルを上げようとしている。

ダンジョンは $N$ 個ある。$i$ 番目のダンジョンの難易度は、2つの整数 $A_i,B_i$ で表される。現在のレベルが $X$ のときに $i$ 番目のダンジョンに挑戦すると、結果は次のようになる。

• $X \le A_i$ なら攻略に失敗し、レベルは変化しない。
• $B_i \le X$ なら攻略に成功し、レベルが $$ 増加する。

一度挑戦したダンジョンには再び挑戦できない。挑戦するダンジョンの順序と個数は自由に決められる。

ビタロの初期レベルは $L$ である。最初に与えられたダンジョンの状態、および各更新クエリを適用した後の状態について、レベル $L$ から開始して到達できるレベルの最大値をそれぞれ求めよ。

各答えを求めるとき、ビタロは必ずレベル $L$ から開始し、すべてのダンジョンはまだ挑戦されていない状態である。ある答えを求める過程で行った挑戦は、別の答えを求める過程には影響しない。

各更新クエリは3つの整数 $i,a,b$ で与えられる。クエリを適用すると、$i$ 番目のダンジョンの難易度は $A_i=a$, $B_i=b$ に変更される。変更後の値は後続のクエリにも引き継がれる。

入力は次の形式で標準入力から与えられる。

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

$Q+1$ 行出力せよ。

1行目には、更新クエリを1つも適用していない状態で到達できるレベルの最大値を出力する。

$1 \le q \le Q$ について、$q+1$ 行目には最初の 個の更新クエリを適用した後に到達できるレベルの最大値を出力する。

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