{"raw_statement":[{"iden":"statement","content":"Very soon there will be a parade of victory over alien invaders in Berland. Unfortunately, all soldiers died in the war and now the army consists of entirely new recruits, many of whom do not even know from which leg they should begin to march. The civilian population also poorly understands from which leg recruits begin to march, so it is only important how many soldiers march in step.\n\nThere will be _n_ columns participating in the parade, the _i_\\-th column consists of _l__i_ soldiers, who start to march from left leg, and _r__i_ soldiers, who start to march from right leg.\n\nThe beauty of the parade is calculated by the following formula: if _L_ is the total number of soldiers on the parade who start to march from the left leg, and _R_ is the total number of soldiers on the parade who start to march from the right leg, so the beauty will equal |_L_ - _R_|.\n\n**No more than once** you can choose one column and tell **all the soldiers** in this column to switch starting leg, i.e. everyone in this columns who starts the march from left leg will now start it from right leg, and vice versa. Formally, you can pick no more than one index _i_ and swap values _l__i_ and _r__i_.\n\nFind the index of the column, such that switching the starting leg for soldiers in it will maximize the the beauty of the parade, or determine, that no such operation can increase the current beauty."},{"iden":"input","content":"The first line contains single integer _n_ (1 ≤ _n_ ≤ 105) — the number of columns.\n\nThe next _n_ lines contain the pairs of integers _l__i_ and _r__i_ (1 ≤ _l__i_, _r__i_ ≤ 500) — the number of soldiers in the _i_\\-th column which start to march from the left or the right leg respectively."},{"iden":"output","content":"Print single integer _k_ — the number of the column in which soldiers need to change the leg from which they start to march, or 0 if the maximum beauty is already reached.\n\nConsider that columns are numbered from 1 to _n_ in the order they are given in the input data.\n\nIf there are several answers, print any of them."},{"iden":"examples","content":"Input\n\n3\n5 6\n8 9\n10 3\n\nOutput\n\n3\n\nInput\n\n2\n6 5\n5 6\n\nOutput\n\n1\n\nInput\n\n6\n5 9\n1 3\n4 8\n4 5\n23 54\n12 32\n\nOutput\n\n0"},{"iden":"note","content":"In the first example if you don't give the order to change the leg, the number of soldiers, who start to march from the left leg, would equal 5 + 8 + 10 = 23, and from the right leg — 6 + 9 + 3 = 18. In this case the beauty of the parade will equal |23 - 18| = 5.\n\nIf you give the order to change the leg to the third column, so the number of soldiers, who march from the left leg, will equal 5 + 8 + 3 = 16, and who march from the right leg — 6 + 9 + 10 = 25. In this case the beauty equals |16 - 25| = 9.\n\nIt is impossible to reach greater beauty by giving another orders. Thus, the maximum beauty that can be achieved is 9."}],"translated_statement":[{"iden":"statement","content":"很快，伯兰将举行一场庆祝战胜外星入侵者的阅兵式。但不幸的是，所有士兵都在战争中阵亡，现在军队完全由新兵组成，其中许多人甚至不知道应该从哪条腿开始行进。平民群众也不清楚新兵应该从哪条腿开始行进，因此唯一重要的是有多少士兵能保持步调一致。\n\n将有 #cf_span[n] 个方阵参加阅兵，第 #cf_span[i] 个方阵包含 #cf_span[li] 名从左腿开始行进的士兵和 #cf_span[ri] 名从右腿开始行进的士兵。\n\n阅兵的美感由以下公式计算：设 #cf_span[L] 为所有从左腿开始行进的士兵总数，#cf_span[R] 为所有从右腿开始行进的士兵总数，则美感等于 #cf_span[|L - R|]。\n\n你最多可以进行一次操作：选择一个方阵，并命令该方阵中的所有士兵交换开始行进的腿——即原本从左腿开始的士兵现在从右腿开始，反之亦然。形式上，你可以选择至多一个下标 #cf_span[i]，并交换 #cf_span[li] 和 #cf_span[ri] 的值。\n\n请找出一个方阵的编号，使得对该方阵中的士兵交换开始行进的腿后，阅兵的美感最大化；或者确定当前美感已达到最大，无需任何操作。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——方阵的数量。\n\n接下来的 #cf_span[n] 行每行包含一对整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li, ri ≤ 500]）——分别表示第 #cf_span[i] 个方阵中从左腿和右腿开始行进的士兵人数。\n\n请输出一个整数 #cf_span[k] —— 需要让士兵交换开始行进腿的方阵编号，若当前美感已最大，则输出 #cf_span[0]。\n\n假设方阵按输入顺序编号为 1 到 #cf_span[n]。\n\n如果有多个答案，输出任意一个即可。\n\n在第一个例子中，如果不进行任何操作，从左腿开始行进的士兵总数为 #cf_span[5 + 8 + 10 = 23]，从右腿开始的为 #cf_span[6 + 9 + 3 = 18]，此时美感为 #cf_span[|23 - 18| = 5]。\n\n如果对第三个方阵进行交换操作，则从左腿开始行进的士兵总数变为 #cf_span[5 + 8 + 3 = 16]，从右腿开始的变为 #cf_span[6 + 9 + 10 = 25]，此时美感为 #cf_span[|16 - 25| = 9]。\n\n无法通过其他操作获得更大的美感，因此能达到的最大美感为 9。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——方阵的数量。接下来的 #cf_span[n] 行每行包含一对整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li, ri ≤ 500]）——分别表示第 #cf_span[i] 个方阵中从左腿和右腿开始行进的士兵人数。"},{"iden":"output","content":"请输出一个整数 #cf_span[k] —— 需要让士兵交换开始行进腿的方阵编号，若当前美感已最大，则输出 #cf_span[0]。假设方阵按输入顺序编号为 1 到 #cf_span[n]。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入\n3\n5 6\n8 9\n10 3\n输出\n3\n\n输入\n2\n6 5\n5 6\n输出\n1\n\n输入\n6\n5 9\n1 3\n4 8\n4 5\n23 54\n12 32\n输出\n0"},{"iden":"note","content":"在第一个例子中，如果不进行任何操作，从左腿开始行进的士兵总数为 #cf_span[5 + 8 + 10 = 23]，从右腿开始的为 #cf_span[6 + 9 + 3 = 18]，此时美感为 #cf_span[|23 - 18| = 5]。\n如果对第三个方阵进行交换操作，则从左腿开始行进的士兵总数变为 #cf_span[5 + 8 + 3 = 16]，从右腿开始的变为 #cf_span[6 + 9 + 10 = 25]，此时美感为 #cf_span[|16 - 25| = 9]。\n无法通过其他操作获得更大的美感，因此能达到的最大美感为 9。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of columns.  \nFor each column $ i \\in \\{1, \\dots, n\\} $, let $ l_i, r_i \\in \\mathbb{Z}^+ $ denote the number of soldiers starting with the left and right leg, respectively.  \n\nDefine:  \n- $ L = \\sum_{i=1}^n l_i $: total soldiers starting with left leg.  \n- $ R = \\sum_{i=1}^n r_i $: total soldiers starting with right leg.  \n- $ \\Delta = |L - R| $: current beauty.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq l_i, r_i \\leq 500 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nLet $ \\Delta' $ be the beauty after swapping $ l_i $ and $ r_i $ in a single column $ i $.  \nSwapping in column $ i $ changes:  \n- $ L \\to L - l_i + r_i $  \n- $ R \\to R - r_i + l_i $  \n- New difference: $ D_i = |(L - l_i + r_i) - (R - r_i + l_i)| = |L - R + 2(r_i - l_i)| $  \n\nFind $ k \\in \\{0, 1, \\dots, n\\} $ such that:  \n- If $ k = 0 $: $ \\Delta $ is maximal (no swap improves beauty).  \n- If $ k \\geq 1 $: $ D_k > \\Delta $, and $ k $ maximizes $ D_k $.  \n\nOutput $ k $ such that $ D_k = \\max_{i \\in \\{0,1,\\dots,n\\}} D_i $, where $ D_0 = \\Delta $.","simple_statement":null,"has_page_source":false}