Andy Jiang studiuje struktury danych. Pewnego dnia jego przyjaciel, Austin Zhu, dał mu zadanie dotyczące drzew.
Austin dostarczył drzewo o $N$ wierzchołkach, ponumerowanych od $1$ do $N$. Każdy wierzchołek $i$ ma przypisaną wartość $A_i$.
Dla każdego zapytania Austin poprosił Andy'ego o rozważenie ścieżki między dwoma wierzchołkami $s_i$ oraz $t_i$ i obliczenie, ile razy dana wartość $x_i$ występuje na tej ścieżce.
Andy rzucił okiem na problem i uznał, że jest on dla niego zbyt łatwy. Zamiast tylko zliczać wystąpienia, postanowił rzucić sobie większe wyzwanie. Dla każdego zapytania chce wiedzieć, jak częstość występowania $x_i$ wypada na tle innych wartości na tej samej ścieżce.
Formalnie, dla każdego zapytania $(s_i, t_i, x_i)$: Rozważ prostą ścieżkę od $s_i$ do $t_i$. Niech $cnt(y)$ oznacza liczbę wystąpień wartości $y$ na tej ścieżce.
Andy definiuje rangę $x_i$ jako: $$1 + |\{y \mid cnt(y) > cnt(x_i)\}|$$
Oznacza to jeden plus liczba różnych wartości, które występują na ścieżce częściej niż $x_i$. Zauważ, że możliwe jest, iż wartość $x_i$ nie występuje na ścieżce, tzn. $cnt(x_i) = 0$. W takim przypadku należy zwrócić jeden plus liczbę różnych wartości występujących na ścieżce.
W niektórych przypadkach testowych zapytania są podane w formie zakodowanej, zgodnie z poniższym opisem.
Pomóż Andy'emu obliczyć rangę $x_i$ dla każdego zapytania.
Wejście
Pierwsza linia zawiera trzy liczby całkowite dodatnie $N$, $Q$ oraz $T$ ($1 \le N, Q \le 10^5$, $T \in \{0, 1\}$). Druga linia zawiera $N$ liczb całkowitych $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$). Następne $N - 1$ linii zawiera po dwie liczby całkowite $u_i, v_i$ ($1 \le u_i, v_i \le N$), reprezentujące $i$-tą krawędź. Każda z kolejnych $Q$ linii zawiera trzy liczby całkowite $\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$), opisujące $i$-te zapytanie.
Niech $last_0 = 0$. Dla każdego zapytania $i = 1, 2, \dots, Q$, rzeczywiste parametry są zdefiniowane jako: $$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$$
Po obliczeniu odpowiedzi na $i$-te zapytanie, przyjmij: $$last_i = \text{odpowiedź na } i\text{-te zapytanie.}$$
Warto zauważyć, że „mod” odpowiada operatorowi % w większości języków programowania, oznaczając resztę z dzielenia. Na przykład $5 \pmod 3 = 2$ oraz $17 \pmod 4 = 1$.
Wyjście
Dla każdego zapytania wypisz odpowiedź w nowej linii.
Podzadania
Poniższa tabela przedstawia rozkład 25 dostępnych punktów:
| Przyznane punkty | Ograniczenia na $N, Q$ | Ograniczenia na $T$ | Dodatkowe ograniczenia |
|---|---|---|---|
| 1 punkt | $1 \le N, Q \le 10^3$ | $T = 1$ | Brak |
| 1 punkt | $1 \le N, Q \le 10^5$ | $T = 0$ | Wszystkie $s_i$ są równe |
| 4 punkty | $1 \le N, Q \le 10^5$ | $T = 1$ | Brak |
| 4 punkty | $1 \le N, Q \le 10^5$ | $T = 0$ | $u_i = i$ oraz $v_i = i + 1$ |
| 5 punktów | $1 \le N, Q \le 10^5$ | $T = 1$ | $u_i = i$ oraz $v_i = i + 1$ |
| 3 punkty | $1 \le N, Q \le 10^5$ | $T = 0$ | Brak |
| 7 punktów | $1 \le N, Q \le 10^5$ | $T = 1$ | Brak |
Przykład
Wejście 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
Wyjście 1
2 1 4 1 1
Wejście 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
Wyjście 2
2 1 4 1 1