W grafie płaskim znajduje się $n$ wierzchołków i $m$ odcinków. Współrzędne $i$-tego wierzchołka wynoszą $(x_i, y_i)$, a $j$-ty odcinek łączy wierzchołki $u_j$ i $v_j$. Odcinek posiada wagę $h_j$ i poza wierzchołkami $u_j$ oraz $v_j$ nie przechodzi przez żadne inne wierzchołki. Jeśli dowolne dwa odcinki mają punkt wspólny, to punkt ten musi być wierzchołkiem, w którym oba te odcinki się stykają. Dla dowolnych dwóch wierzchołków $x$ i $y$ zawsze istnieje ciąg wierzchołków $a_1, a_2, \dots, a_k$ taki, że $a_1 = x, a_k = y$ oraz dla każdego $1 \leq i < k$ wierzchołki $a_i$ i $a_{i + 1}$ są połączone bezpośrednio odcinkiem.

Te $m$ odcinków dzieli płaszczyznę na kilka obszarów, z których tylko jeden jest nieskończony, a pozostałe są ograniczone. Obszar nieskończony nazywamy strefą zakazaną.

Dano $q$ zapytań. W każdym zapytaniu podane są dwa punkty $A$ i $B$ na płaszczyźnie, które nie są wierzchołkami i nie leżą na żadnym z odcinków. Należy wyznaczyć krzywą łączącą $A$ i $B$, która nie przechodzi przez strefę zakazaną ani przez żaden wierzchołek, tak aby maksymalna waga odcinka przeciętego przez tę krzywą była jak najmniejsza. Dla każdego zapytania należy podać tę minimalną wartość.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n$ i $m$, oznaczające odpowiednio liczbę wierzchołków i liczbę odcinków.

W kolejnych $n$ liniach znajdują się po dwie liczby całkowite $x_i, y_i$, oznaczające współrzędne wierzchołka $i$.

W kolejnych $m$ liniach znajdują się po trzy liczby całkowite $u, v, h$, oznaczające odcinek łączący wierzchołki $u$ i $v$ o wadze $h$, gdzie $u \neq v$.

W kolejnej linii znajduje się liczba całkowita $q$, oznaczająca liczbę zapytań.

W kolejnych $q$ liniach znajdują się po cztery liczby rzeczywiste $A_x, A_y, B_x, B_y$, oznaczające współrzędne punktów $(A_x, A_y)$ oraz $(B_x, B_y)$ dla każdego zapytania.

Wyjście

Dla każdego zapytania wypisz w osobnej linii jedną liczbę całkowitą będącą odpowiedzią. W szczególności, jeśli można dotrzeć z punktu $A$ do $B$ bez przekraczania żadnej krawędzi, wypisz $0$; jeśli nie istnieje żadna poprawna krzywa, wypisz $-1$.

Przykład

Wejście

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

Wyjście

2
3
-1

Uwagi

(Brak ilustracji)

Ograniczenia

Zadanie składa się z 10 testów. Charakterystyka poszczególnych testów:

Dla wszystkich danych wejściowych spełnione są warunki $5 \leq n, m \leq 100000$, a wagi wszystkich odcinków nie przekraczają $10^9$. Wszystkie współrzędne w zapytaniach są nieujemnymi liczbami rzeczywistymi nieprzekraczającymi $10^7$ i są nieparzystymi wielokrotnościami $0.5$.