general

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

The next N lines of input each contains one integer P_i, 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.

Scoring

Subtask 0: Sample testcases
Subtask 1 (45 pts): N,Q ≤ 1000
Subtask 2 (55 pts): N,Q ≤ 100000

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