题目描述

记 $P(u,v)$ 表示树上从节点 $u$ 到节点 $v$ 依次经过的点组成的序列，包括 $u$ 和 $v$。

记 $dep_u$ 表示在以 $1$ 为树根时，节点 $u$ 的深度（根节点深度为 $0$）。

记 $\operatorname{LCA}(u,v)$ 为树上节点 $u$ 和 $v$ 在以 $1$ 为树根时的最近公共祖先。

抱月有一棵树，树根为 $1$，一共有 $n$ 个节点。其中第 $i$ 个节点的颜色是 $c_i$。她发现，对于一个节点 $x$ 和整数 $k$，如果将 $P(x,1)$ 中所有满足：$dep_y\equiv dep_x \pmod{k}$ 的 $y$ 都拿出来，这些 $y$ 是有意义的。

所以，你需要解决这样一个问题。给定 $m$ 次询问，每次两个整数 $x,k$，求删掉 $P(x,1)$ 中所有满足 $dep_y\equiv dep_x \pmod{k}$ 的 $y$ 后，满足 $dep_z \le dep_x$ 的 $z$ 中不同 $c_z$ 的数量。每次询问独立，也就是说这次删的点在下一次询问会恢复。

如果不理解，请看样例解释。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $c_i$。

接下来 $n-1$ 行，每行两个整数 $u~v$，表示 $u~v$ 之间有连边。

接下来 $m$ 行，每行两个整数 $x_i~k_i$，表示询问。

输出格式

共 $m$ 行，每行一个整数，表示答案。

11 9
3 1 4 8 8 2 6 4 7 5 1
1 2
1 3
1 4
4 9
9 10
9 11
3 5
3 6
5 8
5 7
3 1
4 1
5 2
11 4
10 3
8 2
6 1
7 1
7 2

2
2
5
8
6
7
3
6
7

提示

对于所有测试数据，保证 $1 \le n,m,k_i \le 10^5$，$1 \le u,v,x_i \le n$，$0 \le c_i \le 10^5$。

样例解释

对于第 $1$ 个询问，满足条件的 $y$ 为：$1,3$。删掉之后，满足条件的 $z$ 为：$2,4$。其中 $c_1=2,c_4=8$，所以答案为 $2$。

对于第 $3$ 个询问，满足条件的 $y$ 为：$1,5$。删掉之后，满足条件的 $z$ 为：$2,3,4,6,9$。其中 $c_2=1,c_3=4,c_4=8,c_6=2,c_9=7$，所以答案为 $5$。