AT_abc170_e [ABC170E] Smart Infants

[problemUrl]: https://atcoder.jp/contests/abc170/tasks/abc170_e AtCoder に参加している幼児が $ N $ 人おり、$ 1 $ から $ N $ の番号が付けられています。また、幼稚園が $ 2\times\ 10^5 $ 校あり、$ 1 $ から $ 2\times\ 10^5 $ の番号が付けられています。 幼児 $ i $ のレートは $ A_i $ であり、はじめ幼稚園 $ B_i $ に所属しています。 これから $ Q $ 回にわたって、転園が行われます。 $ j $ 回目の転園では、幼児 $ C_j $ の所属を幼稚園 $ D_j $ に変更します。 ここで、「平等さ」を、AtCoderに参加している幼児が一人以上いるような幼稚園それぞれについて園内で最もレートの高い幼児のレートを求め、その最小値として得られる値とします。 $ Q $ 回それぞれの転園後の平等さを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $ $ C_1 $ $ D_1 $ $ C_2 $ $ D_2 $ $ : $ $ C_Q $ $ D_Q $

$ Q $ 行出力せよ。 $ j $ 行目には、$ j $ 回目の転園の後の平等さを出力せよ。

### 制約 - $ 1\ \leq\ N,Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ C_j\ \leq\ N $ - $ 1\ \leq\ B_i,D_j\ \leq\ 2\ \times\ 10^5 $ - 入力はすべて整数である。 - $ j $ 回目の転園の前後で幼児 $ C_j $ の所属は異なる。 ### Sample Explanation 1 はじめ、幼稚園 $ 1 $ には幼児 $ 1,\ 4 $、幼稚園 $ 2 $ には幼児 $ 2,\ 5 $、幼稚園 $ 3 $ には幼児 $ 3,\ 6 $ が所属しています。 $ 1 $ 回目の転園で幼児 $ 4 $ の所属を幼稚園 $ 3 $ に変更すると、幼稚園 $ 1 $ には幼児 $ 1 $、幼稚園 $ 2 $ には幼児 $ 2,\ 5 $、幼稚園 $ 3 $ には幼児 $ 3,\ 4,\ 6 $ が所属している状態になります。幼稚園 $ 1 $ で最もレートの高い幼児のレートは $ 8 $、幼稚園 $ 2 $ では $ 6 $、幼稚園 $ 3 $ では $ 9 $ です。これらの最小値は $ 6 $ であるので、$ 1 $ 行目には $ 6 $ を出力します。 $ 2 $ 回目の転園で $ 2 $ 番目の幼児の所属を幼稚園 $ 1 $ に変更すると、幼稚園 $ 1 $ には幼児 $ 1,\ 2 $、幼稚園 $ 2 $ には幼児 $ 5 $、幼稚園 $ 3 $ には幼児 $ 3,\ 4,\ 6 $ が所属している状態になります。幼稚園 $ 1 $ で最もレートの高い幼児のレートは $ 8 $、幼稚園 $ 2 $ では $ 2 $、幼稚園 $ 3 $ では $ 9 $ です。これらの最小値は $ 2 $ であるので、$ 2 $ 行目には $ 2 $ を出力します。 $ 3 $ 回目の転園で $ 1 $ 番目の幼児の所属を幼稚園 $ 2 $ に変更すると、幼稚園 $ 1 $ には幼児 $ 2 $、幼稚園 $ 2 $ には幼児 $ 1,\ 5 $、幼稚園 $ 3 $ には幼児 $ 3,\ 4,\ 6 $ が所属している状態になります。幼稚園 $ 1 $ で最もレートの高い幼児のレートは $ 6 $、幼稚園 $ 2 $ では $ 8 $、幼稚園 $ 3 $ では $ 9 $ です。これらの最小値は $ 6 $ であるので、$ 3 $ 行目には $ 6 $ を出力します。