Note: the full solution to this question may involve algorithms or data structures out of the scope of the HKOI syllabus.

Alice, a royal princess of the WYIOI Kingdom is soon to tour her kingdom for a taste of local delicacies. Her kingdom consists of $N$ settlements labelled from $0$ to $N-1$, and $M$ trails, the $i$-th trail directly connects settlements $A_i$ and $B_i$ bidirectionally. It is guaranteed that all settlements are connected $-$ one may traverse from any settlement $A$ to another other settlement $B$ by using one or many trails across the kingdom.

In order to satisfy the princess's sweet tooth, the $i$-th settlement has prepared exactly one delicacy of sweetness value $S_i$.

As the royal prince of the kingdom, you are responsible for planning the tour. After several grueling days, you managed to draft up $Q$ tours: the $i$-th tour starts at settlement $U_i$ and ends at settlement $V_i$ $(U_i \neq V_i)$.

A tour starting at settlement $U_i$ and ending at settlement $V_i$ is any sequence of settlements $p_0, p_1, p_2, \dots, p_{k-1}$ such that:

• $p_0 = U_i$
• $p_{k-1} = V_i$
• There exists a road that directly connects $p_j$ and $p_{j+1}$ for all $0\leq j \leq k-2$.

Note that the settlements $p_j$ in the tour may not be necessarily distinct, and that a tour may pass through $V_i$ without ending immediately.

For each settlement $p_j$ _{$(0\leq j\leq k-1)$} in the tour, Alice tastes the delicacy in that settlement (even if she has been to the settlement before). As the prince, you are very much aware that the princess is a picky eater $-$ she doesn't like her food too sweet yet doesn't like food that aren't sweet enough. In fact, you can determine with confidence that among all delicacies she consumes in the tour (repeated delicacies are counted again), she will like the delicacies with sweetness equal to the median* of $[S_{p_0}, S_{p_1}, \dots, S_{p_{k-1}}]$ the most.

*Important note: The median of a collection of integers $d_0, d_1, \dots, d_k$ is the $\lceil k/2\rceil$-th smallest element of $d$. For example, the median of $[0, 3, 2, 4]$ is $\ 3$, and the median of $[0, 3, 2]$ is $\ 2$.

Obviously, to satisfy the princess's sweet tooth, you would want to maximise the sweetness of the delicacies she likes most $-$ the delicacies with median sweetness.
Your next task is simple: calculate the maximal median sweetness for each of the $Q$ tours, individually among all possible sequences of settlements.

Input

The first line contains three integers, $N$, $M$ and $Q$.
The next line contains $N$ integers $S_i$ which is the sweetness of the delicacy in settlement $i$.
The next $M$ lines contains a pair of integers $A_i$, $B_i$, which are the two settlements the road $i$ directly connects.
The last $Q$ lines contains a pair of integers $U_i$, $V_i$, which are the starting and ending settlements of tour $i$ respectively.

Output

Output $Q$ integers in one line, where the $i$-th integer is the maximal median sweetness for tour $i$.

Constraints

For all cases, $2\leq N\leq 2\times 10^5$, $1\leq M\leq 4\times 10^5$, $1\leq Q\leq 2\times 10^5$, $1\leq S_i\leq 10^9$, $0\leq A_i,B_i,U_j,V_j\leq N-1$, $A_i\neq B_i$, $U_j\neq V_j$.
It is guaranteed that no two roads directly connect the same pair of settlements, and that all settlements are connected.
Subtask 1 (5%): $Q=1, (U_0, V_0)=(0, N-1)$ and there is no direct trail between $0$ and $N-1$, The kingdom is a tree rooted at settlement 0, each settlement $i$ _{$(1\leq i\leq N-1)$} has a parent $par_i$ such that $par_i \lt i$ and $S_{par_i}\leq S_i$.
Subtask 2 (8%): $Q=1, (U_0, V_0)=(0, N-1)$, The kingdom is a chain where each settlement $i$ _{$(0\leq i\leq N-2)$} is directly connected to settlement $i+1$.
Subtask 3 (14%): $Q,N\leq 5000$, The kingdom is a tree.
Subtask 4 (9%): $Q,N\leq 50, M\leq 200$
Subtask 5 (9%): $Q,N\leq 200, M\leq 600$
Subtask 6 (16%): $Q,N\leq 1500, M\leq 6000$
Subtask 7 (19%): It is guaranteed that for all tours $(U_i, V_i)$, the maximal median sweetness is greater than $\min(S_{U_i}, S_{V_i})$.
Subtask 8 (20%): No additional constraints