A hungry rabbit is wandering on a tree with ~N~ nodes, numbered ~1, 2, \dots, N~ when they notice that the ~i~-th node has a carrot with flavour ~F_i~. The rabbit then decides to ask himself ~Q~ times: "If the tree were rooted at node ~u_j~, how many subtrees would have at least ~k_j~ distinct flavours of carrots?" Having overheard this mumbling, you decide to write a program to answer his queries.

Constraints

~1 \le N, Q \le 5 \times 10^5~

~1 \le F_i, u_j, k_j \le N~

The edges form a tree.

Subtask 1 [20%]

~1 \le N, Q \le 2 \times 10^3~

Subtask 2 [50%]

~k_x = k_y~ for all pairs ~(x, y)~.

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains ~2~ space-separated integers, ~N~ and ~Q~.

The second line of input contains ~N~ space-separated integers, ~F_1, F_2, \dots, F_N~.

The next ~N-1~ lines contain ~2~ space-separated integers each, ~a_i~, ~b_i~, indicating there is an edge between ~a_i~ and ~b_i~.

The next ~Q~ lines contain ~2~ space-separated integers each, ~u_j~, ~k_j~.

Output Specification

Output ~Q~ lines, where the ~j~-th line contains the answer to the ~j~-th query.

Sample Input

8 4
2 1 2 1 1 3 3 2
1 2
6 3
6 7
4 2
2 5
3 1
8 6
1 2
3 1
6 4
5 2

Sample Output

3
8
0
5

Explanation

The trees above are labeled with colours representing the flavours of the carrots.

For the first query, the tree is rooted at node ~1~, and we see that the subtrees rooted at nodes ~1, 3, 6~ have at least ~2~ distinct flavours of carrots.

For the second query, all subtrees have at least ~1~ distinct flavour of carrots.

For the third query, none of the subtrees have at least ~4~ distinct flavours of carrots.

For the fourth query, the tree is rooted at node ~5~, and we see that the subtrees rooted at nodes ~1, 2, 3, 5, 6~ have at least ~2~ distinct flavours of carrots.