C: サボテンクエリ

問題文

単純無向グラフで、任意の辺が高々 $1$ つの単純閉路にしか含まれないようなものをサボテングラフと呼ぶことにします。

$N$ 頂点 $M$ 辺の連結なサボテングラフ $G$ が与えられます。

各頂点は $1$ から $N$ まで番号が付いています。

また、$i$ 個目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでおり、コストは $c_i$ です。

グラフ $G$ 上の単純パスのコストを、そのパス上に含まれる全ての辺のコストの XOR と定めます。

以下のような形式の $Q$ 個のクエリに答えてください。

• x_i y_i k_i ― 頂点 $x_i$ と頂点 $y_i$ を繋ぐすべての単純パスのコストを列挙して重複する値を除き、小さい順に並べた列を $d = d_1, d_2, ... , d_L$ としたときに、$d_{k_i}$ を求めよ。ただし、このコスト列 $d$ の長さ $L$ が $k_i$ より小さい場合は $-1$ とする。

制約

• $2 \leq N \leq 10^5$
• $N - 1 \leq M \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• $0 \leq c_i < 2^{30}$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq x_i, y_i \leq N$
• $x_i \neq y_i$
• $1 \leq k_i \leq 2^{30}$
• 与えられるグラフは連結なサボテングラフである。
• 入力は全て整数である。

入力例 1

4 4
1 2 1
1 3 8
3 2 0
1 4 7
4
1 2 1
2 1 2
1 4 1
3 4 1073741824

出力例 1

1
8
7
-1

• 頂点 $1$ から頂点 $2$ への単純パスは、辺 $1$ のみを経由するものと、辺 $2, 3$ を経由するもので、コストはそれぞれ $1$, $8$ です。なので、$1$ つめのクエリの答えは $1$となります。

• 頂点 $2$ から頂点 $1$ への単純パスも上記と同様なので、 $2$ つ目のクエリの答えは $8$ となります。

• 頂点 $1$ から頂点 $4$ への単純パスは、辺 $4$ のみを経由するもののみで、コストは $7$ です。なので、$3$ つ目のクエリの答えは $7$ となります。

• 頂点 $3$ から頂点 $4$ への単純パスは、辺 $2$, $4$ を経由するものと、辺 $3$, $1$, $4$ を経由するもので、コストはそれぞれ $15$, $6$ です。$1073741824$ 番目に小さいコストは存在しないので、$4$ つ目のクエリの答えは $-1$ となります。

入力例 2

13 15
1 2 1
2 3 2
3 4 3
4 5 1
5 1 2
5 6 4
6 7 15
7 8 9
8 6 7
2 9 5
9 10 5
10 2 2
3 11 3
11 12 2
11 13 1
8
12 13 1
1 11 2
9 5 4
2 7 3
6 12 2
9 7 5
10 3 3
3 12 2

出力例 2

3
3
7
10
7
-1
2
-1