$N$个顶点构成的树（无向无环连通图）存在。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。每个顶点都有一个权值。

请编写一个程序执行下面的查询。

• u v k：输出从 $u$ 到 $v$ 的路径上所有顶点权值中第 $k$ 小的权值。

输入格式

第一行给出 $N$（$2 \le N \le 100{,}000$）。

第二行按顺序给出从 $1$ 号顶点到 $N$ 号顶点的权值。

接下来 $N-1$ 行中，每行给出第 $i$ 条边连接的两个顶点编号 $u$ 和 $v$。

下一行给出查询个数 $M$（$1 \le M \le 100{,}000$）。

接下来 $M$ 行中，每行给出一个查询。

所有顶点的权值都是不超过 $1{,}000{,}000$ 的自然数。

输出格式

按顺序将每个查询的结果输出到一行。

样例

输入格式 1

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

输出格式 1

2
8
9
105
7