Энди Цзян изучает структуры данных. Однажды его друг Остин Чжу дал ему задачу на деревьях.
Остин предоставил дерево с $N$ вершинами, пронумерованными от $1$ до $N$. Каждая вершина $i$ имеет значение $A_i$.
Для каждого запроса Остин попросил Энди рассмотреть путь между двумя вершинами $s_i$ и $t_i$ и вычислить, сколько раз заданное значение $x_i$ встречается на этом пути.
Энди взглянул на задачу и подумал, что она слишком проста для него. Вместо того чтобы просто подсчитывать вхождения, Энди решил усложнить себе задачу. Для каждого запроса он хочет знать, как частота $x_i$ соотносится с другими значениями на том же пути.
Формально, для каждого запроса $(s_i, t_i, x_i)$: Рассмотрим простой путь от $s_i$ до $t_i$. Пусть $\text{cnt}(y)$ — количество вхождений значения $y$ на этом пути.
Энди определяет ранг $x_i$ как $$1 + |\{y \mid \text{cnt}(y) > \text{cnt}(x_i)\}|.$$
То есть, единица плюс количество различных значений, которые встречаются на пути чаще, чем $x_i$. Заметим, что возможно, значение $x_i$ не встречается на пути, т.е. $\text{cnt}(x_i) = 0$. В этом случае вы должны вернуть единицу плюс количество различных значений на пути.
В некоторых тестовых случаях запросы даны в закодированном виде, как описано ниже.
Помогите Энди вычислить ранг $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$-й запрос.
Пусть $\text{last}_0 = 0$. Для каждого запроса $i = 1, 2, \dots, Q$ фактические параметры определяются как: $s_i = ((\hat{s}_i + \text{last}_{i-1} \times T - 1) \pmod N) + 1$, $t_i = ((\hat{t}_i + \text{last}_{i-1} \times T - 1) \pmod N) + 1$, $x_i = ((\hat{x}_i + \text{last}_{i-1} \times T - 1) \pmod{10^9}) + 1$.
После вычисления ответа на $i$-й запрос установите: $\text{last}_i = \text{ответ на } i\text{-й запрос}$.
Может быть полезно отметить, что «mod» соответствует оператору % в большинстве языков программирования, обозначающему остаток от деления. Например, $5 \pmod 3 = 2$ и $17 \pmod 4 = 1$.
Подзадачи
В следующей таблице показано распределение 25 баллов:
| Набранные баллы | Ограничения на $N, Q$ | Ограничения на $T$ | Дополнительные условия |
|---|---|---|---|
| 1 балл | $1 \le N, Q \le 10^3$ | $T = 1$ | Нет |
| 1 балл | $1 \le N, Q \le 10^5$ | $T = 0$ | Все $s_i$ равны |
| 4 балла | $1 \le N, Q \le 10^5$ | $T = 1$ | Нет |
| 4 балла | $1 \le N, Q \le 10^5$ | $T = 0$ | $u_i = i$ и $v_i = i + 1$ |
| 5 баллов | $1 \le N, Q \le 10^5$ | $T = 1$ | $u_i = i$ и $v_i = i + 1$ |
| 3 балла | $1 \le N, Q \le 10^5$ | $T = 0$ | Нет |
| 7 баллов | $1 \le N, Q \le 10^5$ | $T = 1$ | Нет |
Выходные данные
Для каждого запроса выведите ответ на новой строке.
Примеры
Примеры 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
Примеры 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 1 4 1 1