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$ 的排名定義為 $$1 + |\{y \mid cnt(y) > cnt(x_i)\}|$$

也就是說，路徑上出現頻率高於 $x_i$ 的相異值數量再加一。請注意，值 $x_i$ 可能不會出現在路徑上，即 $cnt(x_i) = 0$。在這種情況下，你應該回傳路徑上相異值的總數加一。

在某些測試案例中，詢問會以如下所述的編碼形式給出。

請幫助 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$ 行，每行包含兩個整數 $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$ 個詢問。

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

範例輸出 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