时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一棵 \(N\) 个节点的树，每个点有一个权值，对于 \(M\) 个询问 \((u,v,k)\)，你需要回答 \(u\ xor\ lastans\) 和 \(v\) 这两个节点间第 \(K\) 小的点权。其中 \(lastans\) 是上一个询问的答案，初始为 0，即第一个询问的 \(u\) 是明文。

【输入格式】

　　第一行两个整数 \(N,M\)。
　　第二行有 \(N\) 个整数，其中第i个整数表示点 \(i\) 的权值（绝对值不超过 \(10^9\)）。
　　后面 \(N-1\) 行每行两个整数 \((x,y)\)，表示点 \(x\) 到点 \(y\) 有一条边。
　　最后 \(M\) 行每行两个整数 \((u,v,k)\)，表示一组询问。

【输出格式】

　　\(M\) 行，表示每个询问的答案。

【输入输出样例】

　Input

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

　Output

2
8
9
105
7

【数据限制】

　　对于 \(100\%\) 的数据，\(N,M≤100000\)。

【来源】

　　Mr.he