In a planar graph with $n$ vertices and $m$ line segments, the $i$-th vertex has coordinates $(x_i, y_i)$, and the $j$-th line segment connects vertex $u_j$ and vertex $v_j$ with a weight $h_j$. The line segment $j$ does not pass through any other vertices except $u_j$ and $v_j$. If any two line segments have a common point, that point must be a vertex, and both line segments must be connected to that vertex. For any two vertices $x$ and $y$, there always exists a sequence of vertices $a_1, a_2, \dots, a_k$ such that $a_1 = x, a_k = y$, and for any $1 \leq i < k$, $a_i$ and $a_{i + 1}$ are directly connected by a line segment.

These $m$ line segments divide the entire plane into several regions. Only one region is infinite, while the others are bounded. We call the infinite region the "forbidden zone."

You are given $q$ queries. Each query provides two points $A$ and $B$ in the plane that are not vertices and do not lie on any line segment. You need to draw a curve connecting $A$ and $B$ such that the curve does not pass through the forbidden zone or any vertex, and the maximum weight of the line segments crossed by the curve is minimized. For each query, output this minimum possible value.

Input

The first line contains two positive integers $n$ and $m$, representing the number of vertices and the number of line segments, respectively.

The next $n$ lines each contain two integers, where the $i$-th line (the $(i+1)$-th line in total) contains the coordinates $(x_i, y_i)$ of vertex $i$.

The next $m$ lines each contain three positive integers $u, v, h$, representing a line segment connecting vertex $u$ and vertex $v$ with weight $h$, where $u \neq v$.

The next line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain four real numbers $A_x, A_y, B_x, B_y$, representing a query with two points at coordinates $(A_x, A_y)$ and $(B_x, B_y)$.

Output

Output $q$ lines, each containing a single integer representing the answer to each query. Specifically, if no edge needs to be crossed to reach the destination, output $0$; if no valid curve exists, output $-1$.

Examples

Input 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

Output 1

2
3
-1

Note

(No image available)

Constraints

This problem consists of 10 test cases. The scale and characteristics of each test case are as follows:

For all data, $5 \leq n, m \leq 100000$, and the weight of any line segment does not exceed $10^9$. All query coordinates are non-negative real numbers not exceeding $10^7$, and are guaranteed to be odd multiples of $0.5$.