B. Парад
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Совсем скоро в Берляндии состоится парад победы над инопланетными захватчиками. К сожалению, в войне погибли все солдаты, и теперь армия состоит исключительно из новобранцев, многие из которых даже не знают, с какой ноги начинается марш. Гражданское население тоже плохо понимает, с какой ноги начинается марш, поэтому важно лишь, чтобы как можно больше солдат шли в одну ногу.

В параде будут принимать участие n пеших колонн, i-я из которых состоит из li солдат, начинающих марш с левой ноги, и ri солдат, начинающих марш с правой ноги.

Красота парада вычисляется по следующей формуле: если L — это суммарное количество солдат на параде, начинающих марш с левой ноги, а R — это суммарное количество солдат на параде, начинающих марш с правой ноги, то красота будет равна |L - R|.

Вы можете выбрать не более чем одну колонну, и изменить с какой ноги начинают марш все солдаты данной колонны. Формально, разрешается не более одного раза выбрать какой-то индекс i и поменять местами значения li и ri.

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

Входные данные

В первой строке содержится одно число n (1 ≤ n ≤ 105) — количество пеших колонн. В следующих n строках находятся пары целых чисел li и ri (1 ≤ li, ri ≤ 500) — количество солдат в i-й колонне, начинающих марш с левой и с правой ноги соответственно.

Выходные данные

Выведите одно целое число k — номер колонны, в которой следует сменить шаг, или 0, если максимальная красота уже достигнута.

Считайте, что колонны пронумерованы от 1 до n в порядке их задания во входных данных. Если решений несколько, выведите любое.

Примеры
Входные данные
3
5 6
8 9
10 3
Выходные данные
3
Входные данные
2
6 5
5 6
Выходные данные
1
Входные данные
6
5 9
1 3
4 8
4 5
23 54
12 32
Выходные данные
0
Примечание

В первом примере, если вы не дадите приказ какой-либо колонне сменить шаг, то количество солдат, начинающих марш с левой ноги, будет равно 5 + 8 + 10 = 23, а с правой — 6 + 9 + 3 = 18. В таком случае красота парада будет равна |23 - 18| = 5.

Если вы дадите приказ сменить ногу третьей колонне, то количество солдат, марширующих с левой ноги, будет равно 5 + 8 + 3 = 16, а с правой — 6 + 9 + 10 = 25. В таком случае красота парада будет равна |16 - 25| = 9.

Каким-либо другим приказом невозможно достичь большей красоты. Таким образом, максимально достижимая красота равна 9.