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⁶