题目描述

给你一棵 $n$ 个节点的树，每个节点有一种颜色，有 $m$ 次查询操作。

查询操作给定参数 $l ,r ,x$，需输出：

将树中编号在 $[l,r]$ 内的所有节点保留 $x$ 所在连通块中颜色种类数。

每次查询操作独立。

输入格式

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

第二行 $n$ 个数表示每个节点的颜色。

之后 $n-1$ 行，每行两个数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间连有一条边。

之后 $m$ 行，每行三个数 $l,r,x$，表示一次查询操作。

输出格式

对每个查询操作，输出一行一个数表示答案。

输入输出样例

输入 #1

5 4
1 3 5 3 5
1 2
2 3
3 4
4 5
1 5 1
2 4 3
3 4 3
1 4 3

输出 #1

3
2
2
3

数据范围

$1 \le n,m \le 10^5 , l \le x \le r$