该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

stong9070是三国时代一个谋士，穿越到了2099年成了一个信奥教练，为了有效减少信奥学习的annoyance值提高成绩，他计划一次针对所有小学的annoyance值调查。

题目描述

有$N$名小学生在HOJ注册，对应编号从1到$N$,同时有序号从1到$2*10^5$所小学，第$i$个小学生有一个evenness值为$A_i$,开始的时候就读于$B_i$小学。

从现在开始，有$Q$次转学发生，第$j$次转学后，小学生$C_j$转到小学$D_j$。

在这里，我们将annoyance值定义如下：

• 在每个小学中找到所有小学生中的最高evenness值，就是学校的evenness值
• annoyance值被定义为所有小学evenness值中最小的evenness值

对于每一次Q转学，转学后找到annoyance值。

输入格式

第一行两个整数$N,Q$

从第二行到$N+1$行，每行两个整数$A_i,B_i$

接下来$Q$行，每行两个整数$C_i,D_i$

输出格式

输出$Q$行,第$j$行应该包含第$j$次转学之后的annoyance值

样例

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

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小学小学生的最高evenness分别为8、6、9。其中最低的是6，所以输出中的第1行为6。

第2次转学后：小学生2就读于小学1，小学生1、2就读于小学1、小学生5就读于小学2，小学生3、4、6就读于小学3。1、2、3小学小学生的最高evenness分别为8、2、9。其中最低的是2，因此输出中的第2行为2。

第3次转学后：小学生1就读于小学2，小学生2就读于小学1、小学生1、5就读于小学2，小学生3、4、6就读于小学3。1、2、3小学小学生的最高evenness分别为6、8、9。其中最低的是6，所以输出中的第3行为6。

2 2
4208 1234
3056 5678
1 2020
2 2020

3056
4208

数据范围：

• $1 ≤ N,Q ≤ 2 × 10^{5}$
• $1 ≤ A_{i}​ ≤ 10^{9}$
• $1 ≤ C_{j} ​≤ N$
• $1 ≤ B_{i}​ ,D_{j}​ ≤ 2 × 10^{5}$
• 输入中的所有值都是整数
• 在第$j$次转学中，小学生$C_j$改变了他就读的小学