K-th Smallest Weight on a Tree Path

You are given a tree with n nodes where each node is assigned a weight. There are m queries; each query provides three integers u, v, and k. For the first query, use the given u value. For subsequent queries, let last be the answer to the previous query, and let the effective u be u \(\oplus\) last (where \(\oplus\) denotes bitwise XOR).

Your task is to find the k-th smallest weight among the nodes that lie on the unique path between node u \(\oplus\) last and node v in the tree. It is guaranteed that all queries are valid and that k is between 1 and the number of nodes on the path.

Note: The value of last is initially 0. All formulas are represented in \(\LaTeX\) format.

inputFormat

The input begins with a line containing two integers n and m, where n is the number of nodes in the tree and m is the number of queries.

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

Each of the next n-1 lines contains two integers u and v indicating there is an edge between node u and node v.

Each of the following m lines contains three integers u, v, and k representing a query. For the first query, the given u is used directly; for subsequent queries, the effective u is calculated as u \(\oplus\) last, where last is the answer to the previous query.

outputFormat

For each query, output a single integer representing the k-th smallest weight among the nodes on the path between the effective node u and node v.

sample

5 3
1 5 2 6 3
1 2
1 3
2 4
2 5
1 4 2
1 3 1
2 5 3

5
1
3