29500번 - Разрезание торта 스페셜 저지다국어

문제

На второй планете одной звезды принято отмечать дни рождения вдвоем. Вот и на свое 22-летие Ятив пригласил свою лучшую подругу Янат.

Вместе они приготовили замечательный торт в форме выпуклого многоугольника с $N$ вершинами. Теперь им осталось разделить его на две примерно равные по площади части. Но они хотят увеличить суммарное количество углов в двух получившихся кусках всего на два по сравнению с начальным $N,ドル то есть провести разрез через какие-то две несоседние вершины, то есть просто по одной из диагоналей многоугольника.

Конечно же, они хотят разделить торт таким образом, чтобы им достались по возможности наиболее равные по площади части, то есть, чтобы отношение площади меньшего куска к площади большего было как можно ближе к 1ドル$.

입력

Первая строка входного файла содержит целое число $N$ (4ドル \le N \le 10^5$) --- количество вершин многоугольника, форму которого имеет торт.

Следующие $N$ строк содержат по два целых числа $x_i, y_i,ドル не превышающих по модулю 10ドル^9$ --- координаты $i$-ой вершины выпуклого многоугольника в порядке обхода против часовой стрелки. Никакие три последовательные вершины не лежат на одной прямой.

출력

В выходной файл выведите номера вершин, через которые необходимо провести разрез. Вершины пронумерованы в порядке появления во входном файле.

В случае, если оптимальных ответов несколько, выведите любой.

제한

노트

В первом примере торт имеет форму квадрата и не важно по какой диагонали резать --- отношение площадей всегда получается равным единице.