幻光留影

> 为了给大家留下独特的十周年纪念，小 T 和小 S 在主会场中布置了一个大型的交互艺术装置"幻光留影"。 > > 这个装置由许多悬浮的影像结点组成，通过光束连接成了一棵树的形态，并为每个结点配置了不同颜色的光影滤镜。你来到了控制台前，发现这里可以自由互动：每当调节控制台上的参数，系统会临时只激活特定编号区间内的光束，让整个留影网络在半空中分裂成若干个独立的连通子区域。同一连通子区域中的同种滤镜之间会发生光学干涉：当这种滤镜在连通块内出现了偶数次时，它将变得不可见；当出现次数为奇数时，这些滤镜的展现效果与单个这种颜色的滤镜一致。 > > 光影破碎与重组的视觉效果十分迷人。你对其中隐藏的结构变化产生了浓厚的兴趣：在每一次这样的局部激活下，所有被孤立出来的连通区域中，分别包含了多少种不同颜色的可见滤镜呢？

幻光留影装置可抽象为一棵包含 $$$n$$$ 个结点的树，每个结点代表一个影像结点，结点 $$$i \ (1 \le i \le n)$$$ 的滤镜颜色为 $$$c_i$$$。连接结点的光束共有 $$$n - 1$$$ 条，并按照安装顺序依次编号为 $$$1$$$ 到 $$$n - 1$$$。

在你尝试探索规律的过程中，你记录了 $$$m$$$ 次动态效果测试的数据。对于每次测试，你指定了一个光束编号区间 $$$[l, r]$$$。假设此时只保留编号落在该区间内的光束，而断开所有编号不在 $$$[l, r]$$$ 内的光束，原先连通的装置网络便会分裂成若干个独立的连通块。

为了更深入地分析其中的结构变化，你需要针对每一次测试计算出：所有分裂出的连通块中，各自包含的可见滤镜颜色种类数的总和。

Input

输入的第一行包含两个正整数 $$$n, m \ (1 \le n \le 10 ^ 5, \ 1 \le m \le 3\times10 ^ 5)$$$，分别表示影像结点的数量与测试次数。

输入的第二行包含 $$$n$$$ 个正整数 $$$c_1, c_2, \dots, c_n \ (1 \le c_i \le n)$$$，分别表示每个影像结点的滤镜颜色。

接下来 $$$n - 1$$$ 行，第 $$$i \ (1 \le i \le n - 1)$$$ 行包含两个正整数 $$$u_i, v_i \ (1 \le u_i, v_i \le n)$$$，表示编号为 $$$i$$$ 的光束连接的两个结点。

接下来 $$$m$$$ 行，每行包含两个正整数 $$$l, r \ (1 \le l \le r \le n - 1)$$$，表示一次测试的光束编号区间。

Output

输出 $$$m$$$ 行，每行一个正整数，依次表示每次测试中所有分裂出的连通块各自包含的不同可见滤镜颜色种类数的总和。

Example

Input

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

Output