bruce has recently been teleported to a strange new world. Here violence is common and the world has been split into tiny city-states. As such, to enter each city bruce will have to pay a certain entrance fee. Moreover, the only safe way to move through this world is through the roads which connect the cities. However, because cities are very careful, each city will be connected to at most 5 other cities. bruce being new to this world, and thinking ahead, has $Q$ queries for you to calculate the danger of the least dangerous path from city $a_i$ to city $b_i$. Because bruce would not like to be robbed, he wants to pay as little as possible at each city to not seem rich. As such, bruce defines the danger of a path as the largest entrance fee that he will have to pay on that path.

Note: For each query, bruce will start at city $a_i$ and as such will not need to pay the entrance fee of city $a_i$.

Constraints

$2\le N\le {10}^5$

$1\le M,Q\le {10}^5$

$1\le a_i,b_i\le N$

$a_i\ne b_i$

$1\le v_i\le {10}^9$

Each city will be connected to at most 5 other cities.

No city will have a road to itself, and there will only be at max one road between any two cities.

Subtask 1 [15%]

$2\le N\le {10}^3$

$1\le M,Q\le {10}^3$

Subtask 2 [30%]

The road network will always be a tree.

Subtask 3 [55%]

No additional constraints.

Input Specification

The first line of input contains $N$, $M$, and $Q$ representing the number of cities, roads, and queries respectively.

The next line contains $N$ integers $v_i$ indicating the entrance cost of each city.

The next $M$ lines contain two integers $a_i$ and $b_i$ denoting a road from city $a_i$ to $b_i$.

The next $Q$ lines contain two integers $a_i$ and $b_i$ requesting the danger of the least dangerous path from city $a_i$ to city $b_i$.

Output Specification

For each query $a_i$, $b_i$, output the danger of the least dangerous path from city $a_i$ to city $b_i$, and if there is no valid path, output -1.

Sample Input

6 7 5
4 3 2 5 1 3
1 2
2 5
3 1
4 2
5 1
5 4
4 3
1 4
5 3
2 3
1 5
1 6

Sample Output

5
4
4
1
-1

Explanation

One of the least dangerous paths from city $1$ to city $4$ is $1\to 3\to 4$ paying entrance fees of $2$ and $5$ for cities $3$ and $4$ respectively, and having a danger of $5$.

One of the least dangerous paths from city $5$ to city $3$ is $5\to 1\to 3$ paying entrance fees of $4$ and $2$ for cities $1$ and $3$ respectively, and having a danger of $4$.

One of the least dangerous paths from city $2$ to city $3$ is $2\to 1\to 3$ paying entrance fees of $4$ and $2$ for cities $1$ and $3$ respectively, and having a danger of $4$.

One of the least dangerous paths from city $1$ to city $5$ is $1\to 5$ paying an entrance fee of $1$ for city $5$, and having a danger of $1$.

There is no valid path from city $1$ to city $6$, thus the output is -1.