問題文

$N$ 頂点からなる木があり、頂点には $1, 2, …, N$ と番号が振られています。
$i$ 番目の辺 $(1 \leq i \leq N - 1)$ は、頂点 $A_i$ と $B_i$ を結んでおり、$C_i$ の重みを持っています。

また、あなたは木の頂点 $1$ におり、$M$ 匹のモンスターを持っています。
モンスターには「素早さ」と呼ばれるパラメータがあり、$i \: (1 \leq i \leq M)$ 番目のモンスターの素早さは $S_i$ です。

あなたは頂点 $1$ から辺を通ることで別の頂点へ移動することができます。 そして、辺を通った瞬間に以下のイベントが発生します。

• 重みが $x$ の辺を通ったとき、$M$ 匹のモンスターの素早さが $x$ との XOR をとった値に変化する。

ここで、$M$ 匹のモンスターの戦闘力を以下のように定義します。

• $M$ 匹のモンスターの中での素早さの最小値

あなたが達成できる戦闘力の最大値を求めてください。

制約

• $1 \leq N, M \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• $1 \leq C_i < 2^{30}$
• $1 \leq S_i < 2^{30}$
• 与えられるグラフは木である。
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

問題の答えを一行に出力せよ。

入出力例

8 5
3 5 8
3 4 5
2 6 7
5 6 10
7 8 4
1 7 6
1 2 8
5 4 9 5 10

6

以下のようにして戦闘力 $6$ を達成できます。

• 頂点 $1$ から 頂点 $7$ へ移動する。モンスターの素早さはそれぞれ $(3, 2, 15, 3, 12)$ となる。
• 頂点 $7$ から 頂点 $8$ へ移動する。モンスターの素早さはそれぞれ $(7, 6, 11, 7, 8)$ となる。