편히 잠드소서

P-22가 세상을 떠난 뒤 그의 유해를 어떻게 할지를 두고 많은 논의가 있었다. 처음에는 USC 맞은편 자연사박물관에 보관하자는 의견이 나왔다. 그러나 결국 한 원주민 부족이 산타모니카 산맥의 공개되지 않은 장소에서 그를 의식에 따라 매장하기로 했다. 그들이 장소를 어떻게 골랐는지는 정확히 알 수 없다. 아마 먼저 후보 지점을 몇 곳 모은 뒤, 하나 이상의 기준에 따라 가장 좋은 곳을 골랐을 것이다. 자연스러운 기준은 모든 도로와 등산로에서 멀리 떨어진 곳이다. 그래야 매장지가 훼손될 가능성이 낮아진다. P-22도 살아 있을 때 사람을 피하는 편이었다. 이 문제에서는 그런 후보 지점을 고른다.

모든 등산로와 도로는 직선 선분으로 주어진다. 곡선 도로는 이런 선분들의 연속으로 근사할 수 있다. 후보 매장 지점도 함께 주어진다. 모든 등산로와 도로 위의 점까지의 최소 거리가 가장 큰 후보를 고른다.

첫 줄에는 데이터 세트의 개수 $1 ≤ K ≤ 100$이 주어진다. 이어서 아래 형식의 데이터 세트 $K$개가 주어진다.

각 데이터 세트의 첫 줄에는 두 정수 $1 ≤ T, L ≤ 1000$이 주어진다. 각각 등산로와 도로의 개수 $T$, 후보 지점의 개수 $L$이다. 이어서 $L$개의 줄에 $i$번째 후보 매장 지점의 좌표인 실수 $x_i^{(s)}$, $y_i^{(s)}$가 한 줄에 두 개씩 주어진다. 그다음 $T$개의 줄에는 실수 네 개인 $x_j^{(t,1)}$, $y_j^{(t,1)}$, $x_j^{(t,2)}$, $y_j^{(t,2)}$가 주어진다. $j$번째 등산로 또는 도로는 점 $(x_j^{(t,1)}, y_j^{(t,1)})$에서 $(x_j^{(t,2)}, y_j^{(t,2)})$까지 직선으로 이어진다. 모든 좌표는 -1000000.0 이상 1000000.0 이하이다.

각 데이터 세트마다 “Data Set $x$:”를 한 줄에 단독으로 출력한다. 여기서 $x$는 데이터 세트 번호이다. 이어서 가장 가까운 등산로 위의 점까지의 거리가 가장 먼 매장 지점의 번호 $i$를 출력한다. 입력에는 동점이나, 가장 가까운 등산로까지의 거리 차이가 $0.001$ 미만인 근접 동점이 나오지 않는다. 각 데이터 세트 뒤에는 빈 줄을 출력한다.