시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Никита очень любит математические парадоксы. Недавно он заметил, что  $$\frac{2}{3} < \frac{1}{1}; \quad \frac{1}{2} < \frac{6}{11},$$ но при этом если у меньших дробей сложить числители и знаменатели и то же сделать с большими дробями, то получатся дроби $$\frac{2+1}{3+2}=\frac{3}{5} \quad\mbox{ и }\quad \frac{1+6}{1+11} = \frac{7}{12},$$ причем $$\frac{3}{5} > \frac{7}{12}.$$

Тогда Никита выписал в ряд $k$ дробей и хочет выбрать среди них четыре дроби, чтобы выполнялись неравенства $$\frac{m_1}{n_1} \le \frac{m_2}{n_2}; \quad \frac{m_3}{n_3} \le \frac{m_4}{n_4},$$ а величина  $$\frac{m_1+m_3}{n_1+n_3} - \frac{m_2+m_4}{n_2+n_4}$$ была максимальна. Каждую из записанных дробей можно взять только в качестве одной из выбранных четырех. Помогите Никите решить эту сложную задачу.

입력

Первая строка ввода содержит число $k$ --- количество дробей, выписанных Никитой ($4 \le k \le 2000$).

Следующие $k$ строк содержат по два положительных целых числа: для каждой дроби задан ее числитель и знаменатель. Все заданные дроби являются несократимыми. Числитель и знаменатель каждой дроби не превышают $10\,000$.

출력

Выведите четыре различных целых числа: номера дробей, которые следует выбрать в качестве $\frac{m_1}{n_1}$, $\frac{m_2}{n_2}$, $\frac{m_3}{n_3}$ и $\frac{m_4}{n_4}$, соответственно. Дроби пронумерованы от 1 до $n$ в том порядке, в котором они заданы во вводе. Если возможных оптимальных решений несколько, разрешается выдать любое из них.

예제 입력 1

4
1 1
1 2
2 3
6 11

예제 출력 1

2 4 3 1