Andy Jiang はデータ構造を学習しています。ある日、友人の Austin Zhu が彼に木に関する課題を出しました。

Austin は $N$ 個の頂点を持つ木を提供しました。頂点には $1$ から $N$ までの番号が付けられており、各頂点 $i$ には値 $A_i$ が割り当てられています。

各クエリにおいて、Austin は Andy に2つの頂点 $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$ よりも頻繁に出現する異なる値の数に $1$ を加えたものです。なお、値 $x_i$ がパス上に存在しない場合（すなわち $cnt(x_i) = 0$ の場合）もあり得ることに注意してください。その場合、パス上の異なる値の数に $1$ を加えたものを返す必要があります。

一部のテストケースでは、クエリは以下に説明するエンコードされた形式で与えられます。 各クエリに対して $x_i$ の順位を計算するのを手伝ってください。

入力

最初の行には、3つの正の整数 $N, Q, T$ ($1 \le N, Q \le 10^5, T \in \{0, 1\}$) が含まれます。 2行目には、$N$ 個の整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$) が含まれます。 続く $N-1$ 行の各行には、2つの整数 $u_i, v_i$ ($1 \le u_i, v_i \le N$) が含まれ、これらは $i$ 番目の辺を表します。 続く $Q$ 行の各行には、3つの整数 $\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{answer to the } i\text{-th query}$ と設定します。

「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