暂无测试数据。

$n$ 个城市（编号为 $1\sim n$）之间通过 $n-1$ 条道路连通，构成一棵以 $1$ 为根结点的有根树。每个城市拥有一种市花（允许两个或两个以上的城市拥有相同的市花），共有 $m$ 种市花，编号为 $1\sim m$。

蒜头君和花椰妹居住在这些城市中，有些时候他们可以通过电话联系，相约在一个城市中参加信息学集训活动。

共有 $q$ 次活动，每次活动会告诉你蒜头君位于城市 $u$，花椰妹位于城市 $v$，以及一个线索 $k$，然后你需要根据以下规则，计算出他们要在哪一个城市参加信息学集训活动：

• (1). 如果 $u$ 和 $v$ 在树上满足：$u$ 是 $v$ 的祖先或者 $v$ 是 $u$ 的祖先，则他们到深度较浅的城市参加集训活动；
• (2). 不满足 (1) 时，他们到最近的且满足市花为 $k$ 的公共祖先结点城市参加集训活动；
• (3). 不满足 (1)、（2）时，他们到城市 $1$ 参加集训活动。

输入格式

第一行三个正整数 $n, m, q$，含义如题所示。

第二行 $n$ 个数，第 $i$ 个数 $c_i$ 表示第 $i$ 个城市的市花种类。

接下来 $n-1$ 行，每行两个整数 $a, b$，表示编号为 $a,b$ 的城市之间存在一条连通的道路。

接下来 $q$ 行，每行三个整数 $u, v, k$，含义如题所示。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 次询问时的蒜头君和花椰妹要去参加信息学集训的城市编号。

数据范围

对于 $30\%$ 的数据，$1\leq n, m, q \leq 1000$；

对于另外 $20\%$ 的数据，$m = 1, 1 \leq n, q \leq 2\times 10^5$；

对于另外 $30\%$ 的数据，$1 \leq n, q \leq 5\times 10^4$；

对于 $100\%$ 的数据，$1\leq n, m, q \leq 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