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

Background

Special for beginners, ^_^

Description

众所周知，睿爸信奥是全国连锁机构，编号从 $1$ 到 $2\times10^5$ ，分布在全国各地，一个机构的教学能力由其最优秀的教师决定。

有编号从 $1$ 到 $N(\le2\times10^5)$ 的教师，第 $i$ 名教师的能力为 $A_i$，最初属于机构 $B_i$。

接下来会进行 $Q(\le2\times10^5)$ 次调动。在第 $j$ 次，将教师从 $C_j$ 调动到机构 $D_j$。请求出所有还有教师的机构中，教学能力最低的机构的能力值。

Format

Input

第一行两个正整数 $N$ 和 $Q$ 。 接下来 $N$ 行，表示每名教师的能力和所属的初始机构。

再接下来 $Q$ 行，表示每次调动情况。

Output

输出 $Q$ 行。第 $i$ 行输出第 $i$ 次调动后的所有机构的最低能力值。

Samples

3 3
1 1
4 5
1 4
1 1
2 5
3 4

1
1
1

Limitation

1s, 1024KiB for each test case.