You have a rooted tree consisting of $*n*$ vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to $*n*$. Then we represent the color of vertex $*v*$ as $*c*_{*v*}$. The tree root is a vertex with number 1.

In this problem you need to answer to $*m*$ queries. Each query is described by two integers $*v*_{*j*}, *k*_{*j*}$. The answer to query $*v*_{*j*}, *k*_{*j*}$ is the number of such colors of vertices $*x*$, that the subtree of vertex $*v*_{*j*}$ contains at least $*k*_{*j*}$ vertices of color $*x*$.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input

The first line contains two integers $*n*$ and $*m*$ $(2 ≤ *n* ≤ 10^{5}; 1 ≤ *m* ≤ 10^{5})$. The next line contains a sequence of integers $*c*_{1}, *c*_{2}, ..., *c*_{*n*}$ $(1 ≤ *c*_{*i*} ≤ 10^{5})$. The next $*n* - 1$ lines contain the edges of the tree. The $*i*$-th line contains the numbers $*a*_{*i*}, *b*_{*i*}$ $(1 ≤ *a*_{*i*}, *b*_{*i*} ≤ *n*; *a*_{*i*} ≠ *b*_{*i*})$ — the vertices connected by an edge of the tree.

Next $*m*$ lines contain the queries. The $*j*$-th line contains two integers $*v*_{*j*}, *k*_{*j*}$ $(1 ≤ *v*_{*j*} ≤ *n*; 1 ≤ *k*_{*j*} ≤ 10^{5})$.

Output

Print $*m*$ integers — the answers to the queries in the order the queries appear in the input.

Note

A subtree of vertex $*v*$ in a rooted tree with root $*r*$ is a set of vertices ${*u* : *dist*(*r*, *v*) + *dist*(*v*, *u*) = *dist*(*r*, *u*)}$. Where $*dist*(*x*, *y*)$ is the length (in edges) of the shortest path between vertices $*x*$ and $*y*$.