暂无测试数据。

cocoa 和 chino 是两个可爱的女孩子。

一天，她们要一起去参观花展。花展有 $n$ 个花田，从 $1$ 到 $n$ 编号，其中花展的出入口在 $1$ 号花田处。任意两个花田之间有且仅有一条路径。每个花田都有一个牌子，牌子上有一个数字，表示从这里回到出入口需要经过的道路数量。每个花田中仅有一种花，参展的花共有 $m$ 种，从 $1$ 到 $m$ 编号。

为了更有趣一些，她们决定先分头行动，各自寻找漂亮的花。到了某个时间，cocoa 走到了编号为 $u$ 的花田，chino 走到了编号为 $v$ 的花田。她们决定在返回出入口的路上会合。她们会联系后确认双方所在地的牌子上的数字，数字更大的人会先往出入口方向走，另一个人待在原地。如果数字一样，那么 cocoa 走。如果走到了另一个人的所在地，两人就会合了。否则，当走到种着编号为 $k$ 的花的花田或者出入口时，就会停下来，然后重新和另一个人联系，重复之前的过程。

现在她们很好奇，对于不同的 $u, v, k$ ，两人会在哪个花田会合。

输入格式

第一行三个数 $n, m, q$ ；

第二行 $n$ 个数，第 $i$ 个数表示编号为 $i$ 的花田中种的花的种类的编号；

之后 $n-1$ 行，每行两个数 $a, b$ ，表示编号分别为 $a$ 和 $b$ 的花田之间有一条道路；

之后 $q$ 行，每行三个数 $u, v, k$ ，意义如题目所述。

输出格式

输出 $q$ 行，每行一个数表示会合的花田的编号。

数据范围

有 $30\%$ 的数据 $n, m, q \le 1000$ ；

另有 $20\%$ 的数据 $m = 1$，$n, q \le 2 \times 10^5$ ；

另有 $30\%$ 的数据 $n, q \le 5 \times 10 ^ 4$ ；

对于 $100\%$ 的数据 $1 \le n, m, q \le 3 \times 10 ^ 5$ 。

8 3 8
3 2 2 2 1 1 1 1
1 2
2 3
3 4
2 5
4 6
2 7
7 8
7 2 1
8 6 3
8 7 1
7 3 1
8 2 3
6 4 1
7 7 1
5 5 1

2
1
7
1
2
4
7
5