На плоскости заданы $n$ вершин и $m$ прямолинейных отрезков. Координаты $i$-й вершины равны $(x_i, y_i)$, а $j$-й отрезок соединяет вершины $u_j$ и $v_j$ и имеет вес $h_j$. Отрезок $j$ не проходит через другие вершины, кроме $u_j$ и $v_j$. Если любые два отрезка имеют общую точку, то эта точка обязательно является вершиной, и оба отрезка соединяются в этой вершине. Для любых двух вершин $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$ отрезков разбивают плоскость на несколько областей. Только одна из них является бесконечной, остальные — ограниченные. Бесконечную область мы будем называть запретной зоной.

Вам дано $q$ запросов. В каждом запросе заданы две точки $A$ и $B$, которые не являются вершинами и не лежат ни на одном из отрезков. Необходимо провести кривую, соединяющую $A$ и $B$, которая не проходит через запретную зону и не пересекает ни одну вершину, так, чтобы максимальный вес отрезка, который пересекает эта кривая, был минимально возможным. Для каждого запроса найдите это минимальное значение.

Входные данные

Первая строка содержит два целых положительных числа $n$ и $m$ — количество вершин и количество отрезков соответственно.

Следующие $n$ строк содержат по два целых числа: $i$-я строка (всего $i+1$-я строка) содержит координаты $x_i, y_i$ вершины $i$.

Следующие $m$ строк содержат по три целых положительных числа $u, v, h$, означающих, что существует отрезок, соединяющий вершины $u$ и $v$ с весом $h$. При этом $u \neq v$.

Следующая строка содержит целое положительное число $q$ — количество запросов.

Следующие $q$ строк содержат по четыре вещественных числа $A_x, A_y, B_x, B_y$, задающих координаты точек $A(A_x, A_y)$ и $B(B_x, B_y)$ для каждого запроса.

Выходные данные

Выведите $q$ строк, в каждой из которых содержится одно целое число — ответ на соответствующий запрос. В частности, если можно добраться из $A$ в $B$, не пересекая ни одного отрезка, выведите $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$.