题目描述

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$ 的简单路径。
• 令 $\operatorname{cnt}(y)$ 表示值 $y$ 在这条路径上的出现次数。

Andy 将 $x_i$ 的 排名 定义为 $1 + |\{y \mid \operatorname{cnt}(y) > \operatorname{cnt}(x_i)\}|$。

也就是说，$1$ 加上路径上出现次数严格多于 $x_i$ 的不同值的个数。注意，$x_i$ 可能根本不在路径上，即 $\operatorname{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,\ldots,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$ 个查询。

令 $\operatorname{last}_0 = 0$。对每个查询 $i = 1,2,\ldots,Q$，实际参数按下式定义：

$$\begin{aligned} s_i &= ((\hat{s}_i + \operatorname{last}_{i-1} \times T - 1) \bmod N) + 1,\\ t_i &= ((\hat{t}_i + \operatorname{last}_{i-1} \times T - 1) \bmod N) + 1,\\ x_i &= ((\hat{x}_i + \operatorname{last}_{i-1} \times T - 1) \bmod 10^9) + 1. \end{aligned}$$

计算完第 $i$ 个查询的答案后，令

$$\operatorname{last}_i = \text{第 } i \text{ 个查询的答案}。$$

这里可能还需要说明，“mod” 对应于大多数编程语言中的 $\%$ 运算符，表示除法取余。例如，$5 \bmod 3 = 2$，$17 \bmod 4 = 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

2
1
4
1
1

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
1
4
1
1

提示

以下表格展示了可获得的 $25$ 分的分配情况：

分值	$N,Q$ 的范围	$T$ 的范围	额外限制
$1$ 分	$1 \le N,Q \le 10^3$	$T=1$	无。
	$1 \le N,Q \le 10^5$	$T=0$	所有的 $s_i$ 均相等。
$4$ 分	^	$T=1$	^
		$T=0$	$u_i=i$ 且 $v_i=i+1$。
$5$ 分		$T=1$	^
$3$ 分		$T=0$	无。
$7$ 分		$T=1$	^

翻译由 DeepSeek V4 Pro 完成