Description

You're given a rooted tree, with N vertices number from 1...N. The root is vertex 1.

Each vertex has a weight. The weight of vertex i is W[i].

You're given Q queries. For query i, find out the K[i]-th max weight in subtree of vertex V[i].

Input

The first line contains two integer N and Q, which is the number of vertices and number of queries.

The second line contains N integer W[1], W[2], ..., W[N], which is the weight of vertices.

For the following N-1 lines, each line contains two integer A[i], B[i], which means there is an edge between vertex A[i] and B[i].

For the following Q lines, each line contains two interger V[i], Q[i]. Please find out the K[i]-th max weight in subtree of vertex V[i].

 

Constraints

• 2 <= N <= 10⁵
• 0 < W[i] <= 10⁹
• 1 <= A[i], B[i] <= N
• 1 <= Q <= 10⁵
• 1 <= V[i] <= N
• 1 <= K[i] <= 20
• The subtree rooted at vertex V[i] has K[i] or more vertices.

 

 

 

Output

Print Q lines, the i-th line is the answer of i-th query.

Sample Input  Download

Sample Output  Download

Tags

Discuss