비행 허가 요청

세계 초강대국이 지구 반대편으로 공습을 준비하고 있다. 이를 위해 여러 대의 비행기를 다른 대륙 상공으로 보내야 한다. 그 항로 위에 있는 작은 나라 TidyLand는 자국 영공을 통과해도 좋은지 허가 요청을 받았다.

TidyLand의 국경은 볼록 다각형 모양이다. TidyLand의 영공은 여러 개의 구역(segment) 으로 나뉘어 있으며, 각 구역은 하나의 관제소가 감시·관제한다. 구역은 영공의 임의의 점이 그 점에서 가장 가까운 관제소에 의해 관제되도록 나뉘어 있다.

허가 요청에는 비행의 시작 좌표와 끝 좌표가 적혀 있다(두 점 모두 TidyLand 바깥에 있다). 비행기는 일정한 고도를 유지하며 직선으로 비행한다. 모든 관제소의 고도가 같으므로 이 문제는 평면 위에서 다룬다. TidyLand 관제 본부는 이 비행기가 어떤 구역들을 지나가는지, 지나가는 순서대로 알고 싶어 한다.

입력의 첫 부분은 TidyLand의 국경을 나타낸다. 첫 줄에는 국경 다각형을 이루는 변의 개수인 정수 $N$이 주어진다 ($3 \le N \le 20$). 이어지는 $N$개의 줄에는 다각형 꼭짓점의 정수 좌표 $X_{B,i}, Y_{B,i}$가 주어진다 ($1 \le X_{B,i}, Y_{B,i} \le 100$, $i = 1 \dots N$). 꼭짓점은 시계 방향으로 차례로 나열된다.

입력의 둘째 부분은 관제소의 위치를 나타낸다. 먼저 한 줄에 관제소의 개수인 정수 $M$이 주어진다 ($1 \le M \le 20$). 이어지는 $M$개의 줄 중 $i$번째 줄에는 $i$번 관제소의 정수 좌표 $X_{C,i}, Y_{C,i}$가 주어진다. 모든 관제소의 고도는 같다.

마지막 부분은 비행 경로를 나타낸다. 한 줄에 네 정수 $X_1, Y_1, X_2, Y_2$가 주어지며(모두 $0$ 이상 $100$ 이하), $(X_1, Y_1)$은 시작 좌표, $(X_2, Y_2)$는 끝 좌표이다. 두 점 모두 TidyLand 바깥에 있다.

출력은 두 줄로 이루어진다. 첫째 줄에는 비행기가 지나가는 구역의 개수를 출력한다. 둘째 줄에는 비행기가 지나가는 구역들의 번호를, 비행기가 들어가는 순서대로 공백으로 구분하여 출력한다. 관제소(구역)는 입력에 주어진 순서대로 $1$번부터 $M$번까지 번호가 매겨진다.

비행기가 TidyLand의 영공에 전혀 들어가지 않으면, $0$ 하나만 적힌 한 줄을 출력한다.