有n 个盒子，每个盒子开始有有一个珠子。每个珠子有一个价值。
　　现在有一种操作：取出一个非空盒子的价值最大的珠子放入另外一个盒子，并输出这个珠子的价值。

Input
　　第一行两个正整数n 和m，为盒子的个数和操作的个数。
　　第二行n 个非负整数，为每个盒子里最开始有的珠子的价值。
　　接下来m 行，每行两个正整数a 和b，表示将盒子a 的价值最大的珠子放到盒子b 中。

Output
　　输出m 行，每行一个正整数，为每个操作移动的那个珠子的价值。

Sample Input

3 5
5 6 7
1 2
3 2
2 3
2 3
3 1
Sample Output 5
7
7
6
7
Hint
　　每个测试点的数据规模如下

　　所有数据中珠子的价值不超过2^31-1，所有的a,b 满足1≤a,b≤n。
　　由于会发生OLE的问题，最后4组数据范围改为n=90000，m=900000。