问题描述

AtCoder注册了$N$个婴儿，编号为$1$到$N$，有$2 \times 10^5$所幼儿园，编号为$1$到$2 \times 10^5$。婴儿$i$的评级为$A_i$，最初属于幼儿园$B_i$。

从现在开始，将进行$Q$次转移。第$j$次转移后，婴儿$C_j$将属于幼儿园$D_j$。

在此，我们定义"evenness"如下。对于每个至少有一个在AtCoder注册婴儿的幼儿园，让我们找到幼儿园中婴儿的最高评级。"evenness"定义为这些评级中的最低值。

对于每次转移中，找到转移后的"evenness"。

约束条件

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

输入

输入数据从标准输入中按以下格式给出：

$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$次转移后的"evenness"。

示例输入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

最初，婴儿$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$，婴儿$3,4,6$属于幼儿园$3$。在幼儿园$1,2,3$中，婴儿的最高评级分别为$8,2,9$。其中的最低值为$2$，因此输出中的第$2$行应该包含$2$。

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

示例输入2

2 2
4208 1234
3056 5678
1 2020
2 2020

示例输出2

3056
4208