Andy Jiang está estudiando estructuras de datos. Un día, su amigo Austin Zhu le propuso una tarea sobre árboles.
Austin proporcionó un árbol con $N$ vértices, numerados del 1 al $N$. Cada vértice $i$ tiene un valor $A_i$.
Para cada consulta, Austin le pidió a Andy que considerara un camino entre dos vértices $s_i$ y $t_i$, y que calcule cuántas veces aparece un valor dado $x_i$ en ese camino.
Andy echó un vistazo al problema y pensó que esta tarea era demasiado fácil para él.
En lugar de simplemente contar las apariciones, Andy decidió desafiarse a sí mismo. Para cada consulta, quiere saber cómo se compara la frecuencia de $x_i$ con otros valores en el mismo camino.
Formalmente, para cada consulta $(s_i, t_i, x_i)$:
- Considere el camino simple desde $s_i$ hasta $t_i$.
- Sea $cnt(y)$ el número de apariciones del valor $y$ en este camino.
Andy define el rango de $x_i$ como
$$1 + |\{y \mid cnt(y) > cnt(x_i)\}|$$
Es decir, uno más el número de valores distintos que aparecen con mayor frecuencia que $x_i$ en el camino. Tenga en cuenta que es posible que el valor $x_i$ no aparezca en el camino, es decir, $cnt(x_i) = 0$. En este caso, debe devolver uno más el número de valores distintos en el camino.
En algunos casos de prueba, las consultas se proporcionan en una forma codificada como se describe a continuación.
Ayude a Andy a calcular el rango de $x_i$ para cada consulta.
Entrada
La primera línea contiene tres enteros positivos $N$, $Q$ y $T$ ($1 \le N, Q \le 10^5$, $T \in \{0, 1\}$).
La segunda línea contiene $N$ enteros $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
Las siguientes $N - 1$ líneas contienen cada una dos enteros $u_i, v_i$ ($1 \le u_i, v_i \le N$), que representan la $i$-ésima arista.
Cada una de las siguientes $Q$ líneas contiene tres enteros $\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$), que describen la $i$-ésima consulta.
Sea $last_0 = 0$. Para cada consulta $i = 1, 2, \dots, Q$, los parámetros reales se definen como:
$$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$$
Después de calcular la respuesta a la $i$-ésima consulta, establezca:
$$last_i = \text{respuesta a la } i\text{-ésima consulta.}$$
Puede ser útil notar que "mod" corresponde al operador % en la mayoría de los lenguajes de programación, indicando el resto después de la división. Por ejemplo, $5 \pmod 3 = 2$ y $17 \pmod 4 = 1$.
La siguiente tabla muestra cómo se distribuyen las 25 marcas disponibles:
| Marcas otorgadas | Límites en $N, Q$ | Límites en $T$ | Restricciones adicionales |
|---|---|---|---|
| 1 marca | $1 \le N, Q \le 10^3$ | $T = 1$ | Ninguna. |
| 1 marca | $1 \le N, Q \le 10^5$ | $T = 0$ | Todos los $s_i$ son iguales. |
| 4 marcas | $1 \le N, Q \le 10^5$ | $T = 1$ | Todos los $s_i$ son iguales. |
| 4 marcas | $1 \le N, Q \le 10^5$ | $T = 0$ | $u_i = i$ y $v_i = i + 1$. |
| 5 marcas | $1 \le N, Q \le 10^5$ | $T = 1$ | $u_i = i$ y $v_i = i + 1$. |
| 3 marcas | $1 \le N, Q \le 10^5$ | $T = 0$ | Ninguna. |
| 7 marcas | $1 \le N, Q \le 10^5$ | $T = 1$ | Ninguna. |
Salida
Para cada consulta, imprima la respuesta a la consulta en una nueva línea.
Ejemplos
Entrada 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
Salida 1
2 1 4 1 1
Entrada 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
Salida 2
2 1 4 1 1