텍사스의 여름

텍사스의 여름은 아주 덥다. 이제 막 텍사스로 온 컴퓨터공학과 학생은 이 더위에 익숙하지 않아서, 기숙사에서 강의실까지 걸어가는 동안 땀을 흘린다.

학생은 햇볕 아래에 있는 동안에만 땀을 흘린다. 땀의 양은 쉬지 않고 햇볕을 쬔 시간의 제곱에 비례한다. $s$초 동안 계속 햇볕을 쬐면 $Cs^2$갤런을 흘리며, 상수 $C$는 학생마다 다르다. 그늘에 들어서면 노출이 끊기고 땀도 곧바로 멈춘다. 학생은 그늘에서 완전히 식을 때까지 쉬었다가 다시 출발하고, 그늘을 떠나는 순간 노출 시간은 0에서 다시 센다.

걷는 속도는 어디서나 같으므로, 길이가 $d$인 직선 구간 하나에서 흘리는 땀은 $d^2$으로 잰다. $C$는 전 구간에서 같아서 어느 경로가 최선인지에는 영향을 주지 않는다.

학생은 기숙사에서 자신이 고른 그늘로, 고른 순서대로 직선으로 이동한 뒤 강의실로 간다. 땀의 총량이 가장 적은 경로를 구하라.

첫 줄에 그늘의 개수 $n$이 주어진다. ($0 \le n \le 2500$)

다음 $n$개 줄에는 그늘 한 곳의 좌표를 나타내는 정수 $x$와 $y$가 주어진다. 좌표가 같은 그늘은 없다.

이어서 같은 형식으로 두 줄이 더 주어지며, 각각 기숙사와 강의실의 좌표다.

모든 좌표는 $-1000 \le x, y \le 1000$을 만족한다. 기숙사와 강의실은 그늘과 같은 점에 있을 수도 있고, 둘이 서로 같은 점일 수도 있다.

학생이 들르는 그늘의 번호를 순서대로 한 줄에 하나씩 출력한다. 번호는 입력에 주어진 순서를 따르고 0부터 시작한다. 땀이 가장 적은 경로가 그늘을 하나도 지나지 않으면 - 하나만 출력한다.

땀의 총량이 최소인 경로가 여럿이면 번호 수열이 사전순으로 가장 앞서는 것을 출력한다. 두 수열은 처음으로 달라지는 자리의 번호로 비교하고, 한 수열이 다른 수열의 접두사이면 짧은 쪽이 앞선다. 그래서 총량이 같다면 빈 경로가 다른 어떤 경로보다 앞선다.