Description

Given a tree with $n$ nodes, each node has a weight. There are $m$ queries. For each query, you are given $u, v, k$, and you need to answer the $k$-th smallest node weight on the path between $u \text{ xor last}$ and $v$.

Here, $\text{last}$ is the answer to the previous query, initially defined as $0$, i.e., in the first query, $u$ is not xored.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, where the $i$-th integer denotes the weight of node $i$.

Each of the next $n - 1$ lines contains two integers $x, y$, indicating that there is an edge between node $x$ and node $y$.

Each of the last $m$ lines contains three integers $u, v, k$, representing one query.

Output Format

Output $m$ lines, each containing a positive integer, which is the answer to each query.

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

2
8
9
105
7

Hint

Constraints:
For $100\%$ of the testdata, $1 \le n, m \le 10^5$, and node weights are in $[1, 2 ^ {31} - 1]$.

Please refrain from brute force...

Source: bzoj2588 Spoj10628.

The testdata for this problem is self-made by Luogu, generated using CYaRon in 5 minutes.

Translated by ChatGPT 5