Shan is a kind of fish and looks very beautiful in dress.

There is a tree whose root is 1. Every node i in this tree owns a weight , satisfying that if  is an ancestor of  then .

Shan have several questions, each question can be represented as a pair(x,k), Shan wants to find the biggest node y such that .

Shan is not happy today, can you help her to answer these questions?

输入描述:

First line two integers:  and 
Second line n integers, the  integer represents 
Next n-1 lines, two integers each line u and v meaning that there an edge between u and v.
Next m lines, two integers each line and  representing a question.

输出描述:

m lines. One integer each line,  integer represents the answer to  question, and output 0 if there is no such node.

5 5
1 3 4 3 5
1 2
2 3
2 4
1 5
1 1
2 3
3 -3
4 1
5 2

2
4
0
4
5