Requiescat in Pace

After P-22’s death, there was considerable discussion about what should happen to his remains. At first, storing them in the Natural History Museum (across from USC) was proposed. In the end, a native tribe decided to give him a ritualistic burial at an undisclosed location in the Santa Monica Mountains. We do not know exactly how they chose the spot. They probably collected a few candidate locations first, then picked the best one according to one or more criteria. A natural criterion is to be far from all roads and hiking trails, so that the burial site is less likely to be disturbed. P-22 also mostly avoided people while alive. Here, you will choose such a candidate location.

All trails and roads are given as straight line segments. Curved roads can be approximated by a sequence of such segments. You are also given the candidate burial locations. Select the candidate that maximizes the minimum distance to any point on any trail or road.

The first line contains the number $1 ≤ K ≤ 100$ of data sets, followed by the $K$ data sets, each of the following form.

The first line of each data set contains two integers $1 ≤ T, L ≤ 1000$, the number of trails and the number of candidate locations. Then follow $L$ lines, each with two real numbers $x_i^{(s)}$ and $y_i^{(s)}$, the location of the $i$-th candidate burial site. Then follow $T$ lines, each with four real numbers $x_j^{(t,1)}$, $y_j^{(t,1)}$, $x_j^{(t,2)}$, and $y_j^{(t,2)}$. The $j$-th trail or road goes straight from $(x_j^{(t,1)}, y_j^{(t,1)})$ to $(x_j^{(t,2)}, y_j^{(t,2)})$. All coordinates are between $-1000000.0$ and $1000000.0$.

For each data set, print “Data Set $x$:” on a line by itself, where $x$ is the data set number. Then print the index $i$ of the burial site whose distance to its closest point on a trail is largest. Inputs never have ties or near-ties, meaning no two distances to the closest trail differ by less than $0.001$. Print a blank line after each data set.