바이애슬론

각 선수의 두 종목 속도가 주어질 때, 두 트랙 거리를 어떻게 정해도 우승할 수 있는 선수의 번호를 모두 구한다.

보통7기하정렬그리디이분 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

피기가 두 종목으로 이루어진 바이애슬론 대회를 연다. 참가자는 NN명이고, 대회 규칙은 다음과 같다.

  • 참가자 ii의 첫 번째 종목 속력은 V1V_1, 두 번째 종목 속력은 V2V_2이다.
  • 각 참가자는 자기 종목 구간 전체에서 그 속력을 그대로 유지한다.
  • 첫 번째 종목에서 시간 t1t_1 동안 이동하는 거리는 S1=V1t1S_1 = V_1 t_1, 두 번째 종목에서 시간 t2t_2 동안 이동하는 거리는 S2=V2t2S_2 = V_2 t_2이다.
  • 두 종목의 소요 시간 합이 다른 모든 참가자보다 엄격히 작은 참가자가 우승한다.

주최자인 피기는 두 종목의 거리 S1S_1S2S_2를 음이 아닌 실수 중에서 마음대로 정할 수 있다. 어떤 참가자를 우승하게 만드는 S1S_1, S2S_2가 존재하면 그 참가자를 우승 가능자라고 부른다. 우승 가능자를 모두 구하라.

입력

첫째 줄에 참가자 수 NN이 주어진다. (1N2×1051 \le N \le 2 \times 10^5)

다음 NN개 줄에는 참가자 ii의 두 속력 V1V_1V2V_2가 공백으로 구분되어 주어진다. (1V1,V21061 \le V_1, V_2 \le 10^6, i=0,1,,N1i = 0, 1, \dots, N-1)

출력

한 줄에 우승 가능자의 번호를 증가하는 순서로 공백으로 구분해 출력한다. 번호는 0부터 시작한다. 우승 가능자가 한 명도 없으면 이 줄에 -1을 출력한다.