問題文

$N$ 頂点 $M$ 辺の重み付き無向グラフが与えられます。
辺には $1, 2, \dots, M$ と番号が付けられており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結ぶ、長さ $2^{i}$ の辺です。

$Q$ 個の質問に答えてください。$i$ $(1 \leq i \leq Q)$ 個目の質問は、次のような形式です。

• 整数 $x_i, y_i, z_i$ が与えられる。
• 頂点 $x_i$ から頂点 $y_i$ に向かう辺 $z_i$ を通らないパスの中で、長さが最小のものにおける、パスの長さを $10^9 + 7$ で割った余りを求めよ。

入力

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$A_3$ $B_3$
 $\vdots$
$A_M$ $B_M$
$Q$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$x_3$ $y_3$ $z_3$
 $\vdots$
$x_Q$ $y_Q$ $z_Q$

出力

$Q$ 行にわたって出力してください。
$i$ 行目には、$i$ 個目の質問の答えを出力してください。ただし、「頂点 $x_i$ から頂点 $y_i$ に向かう、辺 $z_i$ を通らないパス」が存在しない場合は、その行について $-1$ と出力してください。

制約

• $2 \leq N \leq 200000$
• $1 \leq M \leq 200000$
• $1 \leq A_i < B_i \leq N$
• $(A_i, B_i) \neq (A_j, B_j)$ $[i \neq j]$
• $1 \leq Q \leq 200000$
• $1 \leq x_i < y_i \leq N$
• $1 \leq z_i \leq M$
• どの頂点からどの頂点へも、いくつかの辺を通ってたどり着くことができる
• 入力はすべて整数

サンプル

3 3
1 2
2 3
1 3
3
1 2 1
2 3 1
1 3 1

12
4
8

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

-1
22
8

10 20
1 9
5 9
7 10
4 6
8 9
5 10
3 8
1 6
6 7
3 9
7 9
3 4
5 6
1 7
2 6
6 8
2 5
4 5
3 7
4 10
10
5 6 6
3 10 2
5 8 17
6 9 19
7 8 17
7 9 16
7 10 9
8 10 7
4 10 8
1 4 13

262
938
36
258
108
76
8
100
536
272