Description

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

These $m$ segments divide the plane into several regions. Exactly one region is unbounded and the others are bounded. We call the unbounded region the forbidden region.

You are given $q$ queries. In each query, two arbitrary points $A$ and $B$ in the plane are given; neither is a vertex and neither lies on any segment. Draw a curve connecting $A$ and $B$ that does not pass through the forbidden region or any vertex, and minimize the maximum weight among all segments crossed by the curve. For each query, you need to output this minimal possible value.

Input Format

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

The next $n$ lines each contain two integers. In this part, the $i$-th line (the $(i+1)$-th line overall) contains two integers $x_i, y_i$, the coordinates of vertex $i$.

The next $m$ lines each contain three positive integers $u, v, h$, indicating there is a line segment connecting vertex $u$ and vertex $v$ with weight $h$. Here $u \ne v$.

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

The next $q$ lines each contain four real numbers $A_x, A_y, B_x, B_y$, representing one query whose two points are $(A_x, A_y)$ and $(B_x, B_y)$.

Output Format

Output $q$ lines, each containing an integer, which is the answer for each query in order. If $A$ can reach $B$ without crossing any segment, output $0$. If no valid curve exists, output $-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

2
3
-1

Hint

Sample explanation:

Constraints and notes:

This problem has $10$ test points. The scale and features of each test point are as follows:

For all data, it holds that $5 \le n, m, q \le 100000$. All segment weights do not exceed $10^9$. All query coordinates are real numbers not exceeding $10^7$, and are guaranteed to be multiples of $0.5$.

Translated by ChatGPT 5