미션 임파서블

당신은 적국을 정찰하는 위험한 임무를 맡았다. 적은 나라 곳곳에 레이더 기지를 세워 두었고, 각 레이더는 자신의 원형 탐지 범위 안에 들어온 이동 물체를 즉시 파괴한다.

다행히 정부는 적국의 지도를 건네주었다. 지도에는 모든 레이더의 좌표와 탐지 반지름이 표시되어 있다. 또한 접선해야 할 현지 정보원들의 위치 목록도 가지고 있다. 당신의 임무는 정보원 중 한 명과 접선하는 것이며, 가능하다면 내부 계수(insider-coefficient)가 가장 높은 정보원과 접선하는 것이 좋다.

정보원의 내부 계수란 그 정보원에서 나라의 국경까지의 거리, 즉 정보원의 위치에서 국경 위의 임의의 점까지의 거리 중 최솟값이다. 직관적으로 내부 계수가 가장 높은 정보원은 나라 안쪽으로 가장 깊숙이 자리 잡은 사람이며, 가장 값진 정보를 가지고 있으리라 기대된다.

시작 위치는 항상 점 $(2000, 2000)$이다. 이 지점에서 어떤 정보원의 위치까지, 레이더가 덮고 있는 영역을 단 한 번도 지나지 않고 도달하는 경로가 존재하는지 판정하는 프로그램을 작성하라. 그런 경로가 존재한다면, 위의 내부 계수 기준에 따라 접선해야 할 정보원이 누구인지도 함께 출력해야 한다.

그림 1: 가능한 상황의 예

적국은 (볼록하지 않을 수도 있는) 단순 다각형 모양이다. 다각형이 단순하다는 것은 그 경계가 스스로 교차하지 않는 하나의 닫힌 곡선이라는 뜻이다. 국경은 다각형 꼭짓점들의 나열로 주어진다. 모든 레이더의 중심과 모든 정보원은 국경 안쪽에 있지만, 레이더의 탐지 범위는 국경 바깥까지 뻗을 수 있다.

그림 1에서 정보원 $I_1$은 레이더 탐지 영역 안에 있으므로 접선할 수 없다. 정보원 $I_2$는 모든 레이더 영역 바깥에 있지만, 그에게 가는 어떤 경로도 치명적인 레이더 영역을 지나야 하므로 역시 접선할 수 없다. $I_3$과 $I_4$는 모두 접선할 수 있는데, $I_4$의 내부 계수가 $I_3$보다 크므로 $I_4$가 선택된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 번째 줄은 적국의 국경을 다음 형식으로 나타낸다.

B X1 Y1 X2 Y2 ... XB YB

여기서 $3 \le B \le 1000$은 국경 점의 개수이고, 각 $X_i,Y_i$는 $i$번째 국경 점의 좌표이다. 국경은 점 $i$와 $i+1$ 사이, 그리고 점 $B$와 $1$ 사이를 잇는 선분들로 이루어진다.

두 번째 줄은 정보원들을 다음 형식으로 나타낸다.

N X1 Y1 X2 Y2 ... XN YN

여기서 $1 \le N \le 1000$은 정보원의 수이고, $X_i,Y_i$는 $i$번째 정보원의 좌표이다.

세 번째 줄은 레이더들을 다음 형식으로 나타낸다.

M X1 Y1 R1 X2 Y2 R2 ... XM YM RM

여기서 $1 \le M \le 30$은 레이더의 수이고, $X_i,Y_i$는 $i$번째 레이더의 중심, $R_i$는 그 반지름이다.

모든 좌표는 $0 \le X, Y \le 1000$인 정수이고, 모든 반지름은 $1 \le R \le 1000$인 정수이다. $B = N = M = 0$인 테스트 케이스는 입력의 끝을 의미하며 처리하면 안 된다. 모든 레이더의 중심과 모든 정보원은 국경 안쪽에 있지만, 레이더가 덮는 영역은 국경 바깥까지 뻗을 수 있다.

각 테스트 케이스마다 한 줄을 출력한다. 접선 가능한 정보원이 없으면 Mission impossible을, 있으면 Contact informer K를 출력한다. 여기서 K는 접선 가능한 정보원 중 내부 계수가 가장 높은 정보원의 (입력 순서상) 번호이다. 내부 계수가 가장 높은 정보원이 여럿이면 그중 번호가 가장 작은 것을 선택한다.