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$까지의 단순 경로를 고려합니다.
• $cnt(y)$를 이 경로상에서 값 $y$가 나타나는 횟수라고 합니다.

Andy는 $x_i$의 순위(rank)를 다음과 같이 정의합니다.

$$1 + |\{y \mid cnt(y) > cnt(x_i)\}|$$

즉, 경로상에서 $x_i$보다 더 자주 나타나는 서로 다른 값들의 개수에 $1$을 더한 값입니다. 경로상에 값 $x_i$가 나타나지 않을 수도 있음(즉, $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, \dots, A_N$ ($1 \le A_i \le 10^9$)이 주어집니다. 다음 $N-1$개의 줄에는 각각 $i$번째 간선을 나타내는 두 정수 $u_i, v_i$ ($1 \le u_i, v_i \le N$)가 주어집니다. 다음 $Q$개의 줄에는 각각 $i$번째 쿼리를 설명하는 세 정수 $\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$)가 주어집니다.

$last_0 = 0$이라고 합시다. 각 쿼리 $i = 1, 2, \dots, Q$에 대해, 실제 매개변수는 다음과 같이 정의됩니다.

$$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$$

$i$번째 쿼리에 대한 답을 계산한 후, $last_i = \text{i번째 쿼리의 답}$으로 설정합니다.

대부분의 프로그래밍 언어에서 "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

예제 출력 1

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

2
1
4
1
1