You are given an undirected tree with $N$ nodes and the tree is rooted at node 1. Each node has an integer value $A[i]$ associated with it represented by an array $A$ of size $N$.

Also, you are given $Q$ queries of the following type:

• $u v k$: Find the $k^{th}$ smallest value present on the simple path between node $u$ and node $v$. If the number of nodes on the simple path between node $u$ and node $v$ is less than $k$, then print $-1$.

Input format

• The first line contains two space-separated integers $N Q$ denoting the number of nodes and queries respectively.
• The second line contains $N$ space-separated integers denoting array $A$.
• Next $N - 1$ lines contain two space-separated integers denoting the edges of the tree.
• Next $Q$ lines contain three space-separated integers denoting the queries.

Output format

Print $Q$ space-separated integers denoting the answer of queries.

Constraints

$1 \le N \le 4 \times 10^4 \\ 1 \le Q \le 10^5 \\ 1 \le A[i] \le 10^9 \\ $