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 \\ \)