题目描述

There are $N$ infants registered in AtCoder, numbered $1$ to $N$, and $2\times 10^5$ kindergartens, numbered $1$ to $2\times 10^5$. Infant $i$ has a rating of $A_i$ and initially belongs to Kindergarten $B_i$.

From now on, $Q$ transfers will happen. After the $j$-th transfer, Infant $C_j$ will belong to Kindergarten $D_j$.

Here, we define the evenness as follows. For each kindergarten with one or more infants registered in AtCoder, let us find the highest rating of an infant in the kindergarten. The evenness is then defined as the lowest among those ratings.

For each of the $Q$ transfers, find the evenness just after the transfer.

在 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

样例输入 #1

6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

样例输出 #1

6
2
6

样例 #2

样例输入 #2

2 2
4208 1234
3056 5678
1 2020
2 2020

样例输出 #2

3056
4208

说明

数据规模与约定

• $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$ 更改了其所属的幼儿园。

样例 $1$ 解释

最初，婴儿 $1, 4$ 属于幼儿园 $1$ ，婴儿 $2, 5$ 属于幼儿园 $2$ ，婴儿 $3, 6$ 属于幼儿园 $3$ 。

经过第 $1$ 次转移后，婴儿 $4$ 属于幼儿园 $3$ ，婴儿 $1$ 属于幼儿园 $1$ ，婴儿 $2, 5$ 属于幼儿园 $2$ ，婴儿 $3, 4, 6$ 属于幼儿园 $3$ 。幼儿 $1, 2, 3$ 在幼儿园的最高评分分别为 $8, 6, 9$ 。其中最低的是 $6$ ，因此输出结果中的 $1$ （行）应包含 $6$ 。

经过第 $2$ 次转移后，婴儿 $2$ 属于幼儿园 $1$ ，婴儿 $1, 2$ 属于幼儿园 $1$ ，婴儿 $5$ 属于幼儿园 $2$ ，婴儿{177772767}属于幼儿园 $3$ 。幼儿 $1, 2, 3$ 在幼儿园的评分最高，分别为 $8, 2, 9$ 。其中最低的是 $2$ ，因此输出结果中的 $2$ -nd行应该包含 $2$ 。

经过第 $3$ 次转移后，婴儿 $1$ 属于幼儿园 $2$ ，婴儿 $2$ 属于幼儿园 $1$ ，婴儿 $1, 5$ 属于幼儿园 $2$ ，婴儿 $3, 4, 6$ 属于幼儿园 $3$ 。幼儿 $1, 2, 3$ 在幼儿园的最高评分分别为 $6, 8, 9$ 。其中最低的是 $6$ ，因此输出中的 $3$ -rd行应该包含 $6$ 。