Совсем скоро в Берляндии состоится парад победы над инопланетными захватчиками. К сожалению, в войне погибли все солдаты, и теперь армия состоит исключительно из новобранцев, многие из которых даже не знают, с какой ноги начинается марш. Гражданское население тоже плохо понимает, с какой ноги начинается марш, поэтому важно лишь, чтобы как можно больше солдат шли в одну ногу.
В параде будут принимать участие n пеших колонн, i-я из которых состоит из li солдат, начинающих марш с левой ноги, и ri солдат, начинающих марш с правой ноги.
Красота парада вычисляется по следующей формуле: если L — это суммарное количество солдат на параде, начинающих марш с левой ноги, а R — это суммарное количество солдат на параде, начинающих марш с правой ноги, то красота будет равна |L - R|.
Вы можете выбрать не более чем одну колонну, и изменить с какой ноги начинают марш все солдаты данной колонны. Формально, разрешается не более одного раза выбрать какой-то индекс i и поменять местами значения li и ri.
Найдите номер колонны, при смене шага в которой красота парада станет максимально возможной, или определите, что такой операцией улучшить красоту парада нельзя.
Выходные данные
Выведите одно целое число k — номер колонны, в которой следует сменить шаг, или 0, если максимальная красота уже достигнута.
Считайте, что колонны пронумерованы от 1 до n в порядке их задания во входных данных. Если решений несколько, выведите любое.
Примечание
В первом примере, если вы не дадите приказ какой-либо колонне сменить шаг, то количество солдат, начинающих марш с левой ноги, будет равно 5 + 8 + 10 = 23, а с правой — 6 + 9 + 3 = 18. В таком случае красота парада будет равна |23 - 18| = 5.
Если вы дадите приказ сменить ногу третьей колонне, то количество солдат, марширующих с левой ноги, будет равно 5 + 8 + 3 = 16, а с правой — 6 + 9 + 10 = 25. В таком случае красота парада будет равна |16 - 25| = 9.
Каким-либо другим приказом невозможно достичь большей красоты. Таким образом, максимально достижимая красота равна 9.