Minimizing the Maximum Weight Crossing in a Planar Subdivision

You are given a planar graph defined by n vertices and m line segments. The i-th vertex has coordinates \( (x_i,y_i) \). The j-th segment connects vertex \( u_j \) and vertex \( v_j \) and has a weight \( h_j \). It is guaranteed that apart from its endpoints, a segment does not pass through any other vertex. Moreover, any two segments, if they have a common point, that point is necessarily a vertex (and both segments are incident to it). Furthermore, the graph is connected in the sense that for any pair of vertices \( x \) and \( y \) there exists a sequence of vertices \( a_1,a_2,\dots,a_k \) with \( a_1=x,\ a_k=y \) such that every consecutive pair \( a_i,a_{i+1} \) is directly connected by a segment.

The \( m \) segments partition the whole plane into several regions (faces). Exactly one of these regions is unbounded; we call this unbounded region the forbidden zone. All other regions are bounded and are considered safe.

You are then given q queries. In each query you are given two points \( A \) and \( B \) in the plane (these points are not vertices and do not lie on any segment). Your task is to draw a continuous curve connecting \( A \) and \( B \) such that:

• The curve does not go through any vertex.
• The curve does not enter the forbidden zone (i.e. the unbounded face).
• The curve may cross some segments. However, among the segments that are crossed, let \( X \) be the maximum weight encountered. You want to design the curve so that \( X \) is as small as possible.

For each query, output the minimum possible value of \( X \), i.e. the smallest possible maximum segment weight that must be crossed by any curve satisfying the above conditions.

Note on the formulation: By constructing the dual graph of the bounded faces (each face becomes a node, and two nodes are connected if their corresponding faces share a segment with weight \( h_j \)), the problem is transformed into finding a path (in the dual graph) between the faces containing \( A \) and \( B \) that minimizes the maximum edge weight along the path (a minimax‐path problem). In particular, if \( A \) and \( B \) lie in the same bounded face, the answer is 0.

Geometric guarantees: The input is such that the rotation system is well–defined. You may assume that \( n \), \( m \), and \( q \) are small enough so that a full extraction of the planar subdivision (by sorting edges incident to each vertex and then performing face detection) is feasible.

inputFormat

The input is given as follows:

 n m
 x_1 y_1
 x_2 y_2
 ...
 x_n y_n
 u_1 v_1 h_1
 u_2 v_2 h_2
 ...
 u_m v_m h_m
 q
 A_x A_y B_x B_y
 A_x A_y B_x B_y
 ... (q queries total)

All coordinates are real numbers. It is guaranteed that the given points in queries do not coincide with any vertex and do not lie on any segment.

outputFormat

For each query, output a single integer (or real number) on a separate line, representing the minimum possible value of the maximum segment weight that must be crossed.

sample

4 4
0 0
1 0
1 1
0 1
1 2 2
2 3 3
3 4 4
4 1 1
1
0.5 0.5 0.6 0.6

0