Given a tree with \(N\) vertices and \(N - 1\) edges. \(i^{th}\) node has a value equal to \(A_i\) (array indexing starts from 1). Given $$Q$$ queries of format, $$L$$ $$X$$, find such node which lies at level \(L\mod (Max Depth + 1)\) and has value which is just greater than or equal to $$X$$. Answer to the query is the smallest value of such node and if no such node exists answer is -1.

Note: Root of the tree is 1 and its level is 0, MaxDepth is the maximum depth of the tree.

Input

First line: N, Q i.e no of vertices and no of queries respectively.

Second line: N space separated integers defining array $$A$$

Next N - 1 lines: u and v, meaning there is an edge between vertex u and v.

Next Q lines: Queries of type $$L$$ $$X$$.

Output

For each query, print answer in a new line.

Constraints

\(1 \leq N, Q \leq 2*10^{5}\)

\(1 \leq u,v \leq N\)

\(1 \leq A_i, X \leq 10^9\)

\(0 \leq L \leq N\)