Spoj 10628. Count on a tree

给定一棵包含 $N$ 个节点的树，每个节点都有一个非负整数权值。

你需要回答 $M$ 次询问。每次询问给出 $u,v,k$ ，实际查询的两个端点分别为 $u\mathbin{\mathrm{xor}}\mathrm{lastans}$ 和 $v$ ，其中 $\mathrm{lastans}$ 表示上一次询问的答案，初始值为 $0$ 。对于每次询问，输出这两个端点之间简单路径上第 $k$ 小的节点权值。

输入格式

第一行包含两个整数 $N,M$ 。

第二行包含 $N$ 个整数，其中第 $i$ 个整数表示节点 $i$ 的权值。

接下来 $N-1$ 行，每行包含两个整数 $x,y$ ，表示节点 $x$ 与节点 $y$ 之间有一条边。

最后 $M$ 行，每行包含三个整数 $u,v,k$ ，表示一组询问。该询问实际查询的两个端点为 $u\mathbin{\mathrm{xor}}\mathrm{lastans}$ 和 $v$ 。

输出格式

输出 $M$ 行，每行包含一个整数，表示对应询问的答案。每行均以换行符结束，包括最后一行。

样例输入

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

样例输出

数据范围

$N,M\le 10^5$ ；
所有节点的权值均为非负整数；
每次询问解码后的端点均合法；
对于每次询问， $1\le k\le$ 对应路径包含的节点数。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

输出