19757번 - Парадокс с дробями 스페셜 저지다국어

Никита очень любит математические парадоксы. Недавно он заметил, что $$\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$ в том порядке, в котором они заданы во вводе. Если возможных оптимальных решений несколько, разрешается выдать любое из них.