Ada the Ladybug grows a mulberry tree (which is rooted at node 0). At the beginning, it has a mulberry fruit of distinct size growing on every node. As the time flows, new mulberry fruits appear on each node (additionally - meaning the previous mulberry fruit still remains on given node) - while keeping the condition of distinct sizes.

Ada observes every single fruit and for each new fruit she is asking you to tell her the number of lesser fruits in the subtree of given node.

Input

The first line contains two integers 1 ≤ N, Q ≤ 2*10⁵ , size of mulberry tree.

The next line contains N integers: 0 ≤ A_i ≤ 10⁶, the size of mulberry fruit in each node.

Each of the next N-1 lines contains two integers 0 ≤ a, b < N, meaning the branch (edge) between given nodes.

Each of the next Q lines contains two integers a S: 0 ≤ a < N (the node in which new fruit grows) and 0 ≤ S ≤ 10⁶ (size of the fruit)

Output

For each query, print the number of lesser mulberry fruits which grow in subtree of node where new mulberry fruit grew.

Example Input

7 8
10 9 13 17 11 20 18
0 4
0 1
1 2
1 3
2 5
2 6
0 21
0 8
2 15
3 22
1 14
2 19
0 12
1 16

Example Output

7
0
1
1
2
3
4
4