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.