Given a tree with N vertices and N−1 edges. ith node has a value equal to Ai (array indexing starts from 1). Given Q queries of format, L X, find such node which lies at level Lmod(MaxDepth+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≤N,Q≤2∗105
1≤u,v≤N
1≤Ai,X≤109
0≤L≤N
For query 1: nodes at level 1 are [2, 3] and node with a value just greater than or equal to 6 is 3, whose value is 7.
For query 2: nodes at level 2 are [4, 5, 6] and node with a value just greater than or equal to 7 is 4, whose value is 8.
For query 3: MaxDepth here is 2, so 6 % (2+1) = 0. And at level 0 there is only 1 node i.e 1 whose value is less than 2. So answer is -1.
