Very soon there will be a parade of victory over the alien invaders in Mogotes. Unfortunately, all the soldiers were killed in the war and now the army is fully composed of new recruits, many of whom do not even know which leg should begin a march. The civilian population does not understand which of the legs start to go, so it is only important how many soldiers marching in the parade.

There will be n columns participating in the parade, the i-th column is li soldiers, who begin to march with the left leg, and ri soldiers, who begin to march with the right leg.

The beauty of the parade is calculated by the following formula: if L is the total number of soldiers in the parade starting to march with the left leg, and R is the total number of soldiers in the parade to begin to march with the right leg, beauty is equal to |L - R|.

In order to have the greatest beauty, not more than once, you can choose a column and tell all the soldiers in this column change their starting leg, i.e. everyone in this column that starts up with left leg now begin with the right leg and vice versa. Formally, it can be exchanged, not more than one index i, li values ​​and ri.

Find the index of the column, so that changing the starting leg for soldiers in this column will maximise the beauty, or determine that it is not necessary to change to increase the current beauty.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) - which is the number of columns. The following n lines contain pairs of integers li and ri (1 ≤ li, ri ≤ 500) - the number of soldiers in the ith column begin to march with the left leg or right leg respectively.

Output

Print a single whole number k - the number of the column in which the soldiers need to change leg that begin to march, or 0 if the maximum beauty is already reached. Note that the columns are numbered from 1 to n, in the order in which the input data are given. If there are multiple answers, print any of them.

Example

Input:
3
5 6
8 9
10 3

Output:
3

Input:
2
6 5
5 6

Output:
1

Input:
6
5 9
1 3
4 8
4 5
23 54
12 32

Output:
0

Explanation

In the first example, if you do not give the order to change the starting leg, the number of soldiers, who start marching with the left leg, would be equal to 5 + 8 + 10 = 23, and with the right leg: 6 + 9 + 3 = 18. In this case, the parade beauty will be equal to |23 - 18| = 5.

If the order is given to change the leg with which they start the parade to the third (3) column, the number of soldiers who march with the left leg will be equal to 5 + 8 + 3 = 16, and with the right leg: 6 + 9 + 10 = 25. In this case beauty is equal to |16 - 25| = 9.

It is impossible to reach a greater beauty by giving other orders. Therefore, the maximum beauty that can be achieved is 9.