AT_utpc2011_12.L番目の数字

给出一个图。

• 有$N$个节点，这些节点的编号从$1$到$N$。
• 这些节点通过$N-1$个边缘以树形连接。
• 每个节点$v$都有一个权值$a_v$。

接下来，给出如下格式的$Q$个查询。每个查询$q$，$v_q$，$w_q$和$l_q$。请在所有从节点$v_q$到节点$w_q$的路径中找到节点的第$l_q$个最小值。

• 路径不会两次通过同一顶点。

• 该路径包括两个端点（即顶点$v_q$，$w_q$）。

第一行包含两个整数$N$和$Q$。

接下来$N$行给出每个点具有的权值。每行一个整数$x_v$表示节点$v$的权值。

接下来$N-1$行给出路径信息。第$e$行包含两个整数$a_e$和$b_e$，它们表示连通的两个节点。

下面的$Q$行代表查询信息。第$q$行包含三个整数$v_q$，$w_q$和$l_q$，它们代表查询$q$的信息。

输出由$Q$行组成，第$q$行输出查询$q$的答案。

$1 ≤ N,Q ≤ 10^5$

$1 ≤ x_v ≤ 10^9$

$1 ≤ a_e, b_e ≤ N$

$1 ≤ v_q, w_q ≤ N$

从节点$v_q$到节点$w_q$的路径中至少经过$l_q$个节点。

输入输出样例

输入 #1

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

输出 #1

2
5
7
8
2
4
5
4
5
8
9