You are given a tree with N nodes and each node has some value assigned to it. Now you are given Q tasks of the form X K.
For each task, you have to find the path starting from X such that sum of nodes in the path is at least K and it contains minimum number of nodes. If such path exists, print the count of nodes in the path, else print -1.

Input format

• First line: Two space-separated integers N and Q
  
• Second line: N space-separated integers (denoting val_i)
  
• Next N -1 lines: Two space-separated integers U and V (denoting an edge between the nodes U and V)
  
• Next Q lines:Two space-separated integers X and K
  

Output format

For each task, print the required answer in a new line.

Input Constraints

\(1 \le N \le 10^5\)
\(1 \le Q \le 10\)
\( 1\le val_i \le 10^9\)
\(1 \le U,V \le N\)
\(1 \le X \le N\)
\(1 \le K \le 10^{10}\)