Andy Jiang 正在学习数据结构。有一天，他的朋友 Austin Zhu 给出了一个关于树的任务。

Austin 提供了一棵有 $N$ 个顶点的树，顶点编号从 $1$ 到 $N$。每个顶点 $i$ 都有一个值 $A_i$。

对于每个询问，Austin 要求 Andy 考虑两个顶点 $s_i$ 和 $t_i$ 之间的路径，并计算给定值 $x_i$ 在该路径上出现的次数。

Andy 扫了一眼题目，觉得这个任务对他来说太简单了。

除了仅仅计算出现次数，Andy 决定进一步挑战自己。对于每个询问，他想知道 $x_i$ 的频率与同一路径上其他值的频率相比如何。

形式化地，对于每个询问 $(s_i, t_i, x_i)$： 考虑从 $s_i$ 到 $t_i$ 的简单路径。 令 $cnt(y)$ 为值 $y$ 在该路径上出现的次数。

Andy 定义 $x_i$ 的排名（rank）为： $$1 + |\{y \mid cnt(y) > cnt(x_i)\}|$$

也就是说，路径上出现频率高于 $x_i$ 的不同值的数量加 $1$。注意，值 $x_i$ 可能不会出现在路径上，即 $cnt(x_i) = 0$。在这种情况下，你应该返回路径上不同值的数量加 $1$。

在某些测试用例中，询问以如下所述的编码形式给出。

请帮助 Andy 计算每个询问中 $x_i$ 的排名。

输入格式

第一行包含三个正整数 $N, Q$ 和 $T$ ($1 \le N, Q \le 10^5, T \in \{0, 1\}$)。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$)。 接下来的 $N - 1$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le N$)，表示第 $i$ 条边。 接下来的 $Q$ 行，每行包含三个整数 $\hat{s}_i, \hat{t}_i, \hat{x}_i$ ($1 \le \hat{s}_i, \hat{t}_i \le N, 1 \le \hat{x}_i \le 10^9$)，描述第 $i$ 个询问。

令 $last_0 = 0$。对于每个询问 $i = 1, 2, \dots, Q$，实际参数定义如下： $s_i = ((\hat{s}_i + last_{i-1} \times T - 1) \pmod N) + 1$ $t_i = ((\hat{t}_i + last_{i-1} \times T - 1) \pmod N) + 1$ $x_i = ((\hat{x}_i + last_{i-1} \times T - 1) \pmod {10^9}) + 1$

在计算出第 $i$ 个询问的答案后，设置： $last_i = \text{第 } i \text{ 个询问的答案}$

需要注意的是，“mod”在大多数编程语言中对应 % 运算符，表示除法后的余数。例如，$5 \pmod 3 = 2$ 且 $17 \pmod 4 = 1$。

下表显示了 25 分的分布情况：

输出格式

对于每个询问，在新的一行中输出该询问的答案。

样例

样例输入 1

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

样例输出 1

2
1
4
1
1

样例输入 2

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

样例输出 2

2
1
4
1
1