Энди Цзян изучает структуры данных. Однажды его друг Остин Чжу дал ему задачу на деревьях.

Остин предоставил дерево с $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 баллов:

Выходные данные

Для каждого запроса выведите ответ на новой строке.

Примеры

Примеры 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