CF733B.Parade

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.

There 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.

The 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|.

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.

Find 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.

很快，贝尔兰将举行一场庆祝战胜外星入侵者的胜利游行。不幸的是，所有士兵都在战争中牺牲了，如今军队完全由新招募的士兵组成，其中许多人甚至不清楚应该先迈哪条腿开始行进。普通民众也不太清楚新兵们究竟从哪条腿开始行进，因此唯一重要的是有多少士兵能够步调一致地行进。

游行中将有 $n$ 列队伍参与，第 $i$ 列包含 $l_i$ 名从左腿开始行进的士兵，以及 $r_i$ 名从右腿开始行进的士兵。

游行的“美感”按如下公式计算：设 $L$ 为游行中所有从左腿开始行进的士兵总数，$R$ 为所有从右腿开始行进的士兵总数，则美感值等于 $|L - R|$。

你最多可以执行一次操作：选择某一列，并命令该列中所有士兵切换起始腿——即原本从左腿开始行进的士兵改为从右腿开始，原本从右腿开始行进的士兵改为从左腿开始。形式上，你最多可以选择一个下标 $i$，并交换 $l_i$ 和 $r_i$ 的值。

请找出应选择的列的下标（使得对该列执行上述操作后，游行的美感值达到最大）；若无论如何操作都无法提升当前美感值，则说明不存在这样的操作。

The first line contains single integer n (1 ≤ n ≤ 105) — the number of columns.

The 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示列数。

接下来的 $n$ 行每行包含一对整数 $l_i$ 和 $r_i$（$1 \leq l_i, r_i \leq 500$）—— 分别表示第 $i$ 列中从左腿或右腿开始行进的士兵人数。

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.

Consider that columns are numbered from 1 to n in the order they are given in the input data.

If there are several answers, print any of them.

输出一个整数 $k$ —— 表示士兵需要更换起始迈步腿的列号；若当前已达到最大美观度，则输出 $0$。

注意：列编号按输入数据中给出的顺序从 $1$ 到 $n$ 编号。

若存在多个满足条件的答案，输出任意一个即可。

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.

If 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.

It is impossible to reach greater beauty by giving another orders. Thus, the maximum beauty that can be achieved is 9.

在第一个例子中，如果不下达换腿指令，则从左腿开始行进的士兵人数为 $5 + 8 + 10 = 23$，从右腿开始行进的士兵人数为 $6 + 9 + 3 = 18$。此时阅兵式的“美感”为 $|23 - 18| = 5$。

若向第三列下达换腿指令，则从左腿行进的士兵人数变为 $5 + 8 + 3 = 16$，从右腿行进的士兵人数变为 $6 + 9 + 10 = 25$。此时“美感”为 $|16 - 25| = 9$。

无法通过下达其他指令获得更高的“美感”。因此，所能达到的最大“美感”为 $9$。