In a faraway warring country, there are N generals from different factions engaged in numerous battles.
Each faction has a power from 1 to N, such that a faction with higher power always defeats a faction with
lower power. Indeed, after a faction is defeated by another, all its members are absorbed into the winning
faction. The power of a faction is the maximum of the powers of all its members.
Initially, all generals are in individual factions. You are given the details of M battles between two generals. However, since generals seem to be a very closely-knit bunch, the full strength of the faction will aid in every battle any of its members undertakes. Given the details of these battles, we wish to find out the victorious faction in each battle
Input
The first line of input consists of two integers N and M (1 ≤ N, M ≤ 100,000).
The next N lines of input each contains one integer Pi, representing the power level of the i-th faction. No two factions have the same power level.
The next M lines contain two integers a and b each, indicating that generals a and b have started a battle, which their factions will soon join
Output
For each battle, print out one integer, indicating the faction which has won the battle. If two generals from the same faction fight, it is only considered an internal misunderstanding, and one should print out -1 instead.
Sample Input 1
5 4
1
2
3
4
5
1 5
1 2
1 2
3 4
Sample Output 1
5
5
-1
4