Magry的幸运度

题目描述

已知：左边给出长度为n一串数组$L$，右边给出同样长的一串数$R$，左右两边的数组下标同为i的数（$L_{i}$与$R_{i}$）一一对应且可交换。

另外定义这两组数的幸运度为左边数组L各个元素之和 $ \sum_{i=1}^n L_{i} $ 与右边数组各元素和$\sum_{i=1}^n R_{i}$之差的绝对值，即$\left| \sum_{i=1}^n L_{i} - \sum_{i=1}^n R_{i} \right|$

Magry可以最多对一个数对（即上文提及左右两边的数组下标同为 $i$ 的数$L_{i}$与$R_{i}$）进行交换操作，从而得到新的幸运度$\left| \sum_{i=1}^n L_{i} - \sum_{i=1}^n R_{i} \right|$，也可以选择不对数组进行任何操作。

请问Magry交换第几个数对时得到的幸运度最大？若不交换数对就能得到最大值则输出0。

输入

输入包含多组测试数据，以EOF结束。

对于每组数据，输入n+1行。

第一行为1个正整数，L、R两个数组长度n.

接下来n行，每行2个正整数，以一个空格分隔，对于第 $i$ 个数对，两个数分别表示$L_{i}$与$R_{i}$

需要注意的是，这里$1 \leq i \leq n$

保证$1 \leq n \leq 100000$，$1 \leq L_{i},R_{i} \leq 500$

输出

对于每组数据，输出一行，一个数，Magry交换第几个数对时得到的幸运度最大？若不交换数对就能得到最大值则输出0。

当然，在某些情况下可能存在多种解，输出任意一种解即可。

输入样例

3
5 6
8 9
10 3
2
6 5
5 6

输出样例

第一种答案

3
1

第二种答案

3
2

样例解释

对于上述样例，第二组数据有两种答案，即交换第一个数对或第二个数对均可达到所求幸运度最大(最大值为2)。本题输出任意一种均可。