You are given a weighted tree (an acyclic undirected connected graph) with $N$ nodes. The tree nodes are numbered from 1 to $N$. There are $N-1$ edges with each having a weight assigned to it.

You have to process $Q$ queries on it. In each query, you are given three integers $u,\ v,\ x$. You are required to determine the maximum XOR that you can obtain when you the bitwise XOR operation on any edge weight in the path from node $u$ to node $v$ with $x$.

For example

You are given the following tree:

You get a query $(9,\ 7,\ 1)$. Therefore, in this case, your task is to determine the maximum XOR that you can obtain when you XOR $x$ with any edges in the path from node 9 to node 7.

The path from node 9 to node 7 is marked red for better understanding.

There are 5 edges in the path from node 9 to node 7 and there weight are as follows: $\{4,\ 3,\ 2,\ 10,\ 12\}$. If you XOR 12 with $x$, that is, 12^1 = 13 and this the maximum XOR that you can obtain. Therefore, the answer to this query is 13.

Input format

• The first line contains two space-separated integers $N$ and $Q$.
• The next $N-1$ lines contain three space-separated integers $u,\ v,\ w$ denoting node $u$ and $v$ are connected with an edge of weight $w$.
• The next $Q$ lines contain $u,\ v,\ x$.

Output Format

For each query, print a single integer in a new line.

Constraints

2 $\leq$  N, Q  $\leq$ 10⁵

1 $\leq$ u, v  $\leq$ N  and (u!=v)

1 $\leq$ w, x  $\leq$ 10⁶