平面グラフ上に $n$ 個の頂点と $m$ 本の線分がある。第 $i$ 番目の頂点の座標は $(x_i, y_i)$ であり、第 $j$ 番目の線分は頂点 $u_j$ と頂点 $v_j$ を結び、重み $h_j$ を持つ。線分 $j$ は、頂点 $u_j$ と $v_j$ 以外には他の頂点を通らない。任意の2本の線分が共通点を持つ場合、その共通点は必ず頂点であり、そのとき両方の線分はその頂点に接続している。任意の2つの頂点 $x$ と $y$ について、頂点の列 $a_1, a_2, \dots, a_k$ が存在し、$a_1 = x, a_k = y$ であり、かつ任意の $1 \leq i < k$ に対して $a_i$ と $a_{i + 1}$ が線分で直接結ばれている。

これら $m$ 本の線分は平面をいくつかの領域に分割する。そのうち1つだけが無限に広がる領域であり、残りはすべて有界である。この無限の領域を「禁区」と呼ぶ。

$q$ 回のクエリが与えられる。各クエリでは、平面上の頂点ではなく、かつどの線分上にもない2点 $A$ と $B$ が与えられる。$A$ と $B$ を結ぶ曲線を描くとき、その曲線が禁区およびどの頂点も通らないようにし、かつ通過する線分の重みの最大値を最小化したい。各クエリに対して、この最小値を答えよ。

入力

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

$n$ $m$ $x_1$ $y_1$ $\vdots$ $x_n$ $y_n$ $u_1$ $v_1$ $h_1$ $\vdots$ $u_m$ $v_m$ $h_m$ $q$ $A_{x,1}$ $A_{y,1}$ $B_{x,1}$ $B_{y,1}$ $\vdots$ $A_{x,q}$ $A_{y,q}$ $B_{x,q}$ $B_{y,q}$

1行目には2つの正整数 $n$ と $m$ が与えられ、それぞれ頂点数と線分数を表す。

続く $n$ 行には、各頂点の座標 $(x_i, y_i)$ が与えられる。

続く $m$ 行には、各線分の情報 $u, v, h$ が与えられ、頂点 $u$ と $v$ を結ぶ重み $h$ の線分であることを表す。ここで $u \neq v$ である。

続く1行には、クエリ数 $q$ が与えられる。

続く $q$ 行には、各クエリの2点の座標 $(A_x, A_y)$ と $(B_x, B_y)$ が与えられる。

出力

$q$ 行にわたって、各クエリの答えを順に出力せよ。特に、どの辺も跨がずに到達可能な場合は $0$ を出力し、条件を満たす曲線が存在しない場合は $-1$ を出力せよ。

入出力例

入力 1

9 12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 2 10
2 3 10
3 6 10
6 9 10
9 8 10
8 7 10
7 4 10
4 1 10
2 5 3
5 8 2
5 6 4
4 5 1
3
1.5 1.5 2.5 2.5
1.5 2.5 2.5 1.5
0.5 0.5 1.5 1.5

出力 1

2
3
-1

注記

（画像は現在ありません）

制約

本問題には10個のテストケースがあり、各テストケースの規模と特徴は以下の通りである。

すべてのデータにおいて、$5 \leq n, m \leq 100000$ を満たし、すべての線分の重みは $10^9$ を超えない。すべてのクエリの座標は $10^7$ 以下の非負実数であり、$0.5$ の奇数倍であることが保証されている。