题目描述

给定一个 $n$ 个点的树，从 $1$ 编号至 $n$。编号为 $u$ 的点有点权 $w_u$ 。

总共有 $q$ 次询问，每次给出三个参数 $x,d,k$ 表示询问距离 $x$ 恰好为 $d$ 的点中点权第 $k$ 小的点的编号。若距离 $x$ 恰好为 $d$ 的点的个数不足 $k$ 个则输出 $-1$ 。

输入格式

第一行两个整数 $n,q$ 。

接下来一行，$n$ 个整数 $w_1,...,w_n$ 。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示树中存在一条边 $(u,v)$ 。

接下来 $q$ 行，每行三个整数 $x,d,k$ 表示一组询问。

输出格式

$q$ 行，每行一个整数，表示询问的答案。

测试样例

样例 #1

样例输入 #1

10 10
873066683 798980715 283588869 392158209 686968000 147459219 192754078 263241671 160744327 257199586 
8 10
8 2
8 7
10 4
7 1
4 6
6 3
3 5
5 9
4 2 3
7 2 1
6 1 2
6 1 2
6 1 3
8 2 2
3 1 1
10 1 3
10 1 3
9 1 1

样例输出 #1

-1
10
4
4
-1
1
6
-1
-1
5

提示

保证 $1\le n,q \le 1\times 10^5, 1\le w_i \le 10^9$ 。

保证所有 $w_i$ 均不相同。

对于询问，保证 $1\le x,d,r\le n$ 。

性质 A：对于所有询问，满足 $r=1$ 。

本题开启测试点捆绑和测试点依赖。