操场上有N堆石子，围成一个圈，每堆石子的数量a_1,a_2,...,a_i,...,a_N。

现在有M个人来拿取石子，每个人取走石子的指令包含两个数,d_i和x_i，具体操作如下：

1）对于第1个人，表示从第1堆开始，按逆时针数到第d_1堆，也就是到达第d_1+1堆，取走x_1个石子。如果第d_1+1堆石子数少于x_1，则将第d_1+1堆全部取完，不够部分再到第d_1+2堆拿取，如果还不够，继续从第d_1+3堆拿，直到取够x_1个石子。

2）第1个人取走石子的最后一堆，标记为当前位置p_1。第2个人将从当前位置按逆时针顺序的下一堆开始计数，数到第d_2堆（即第p_1+d_2堆）去拿取x_2个石子。如果第p_1+d_2堆石子不够拿，他依然会往后面堆去拿，直到拿够x_2个。

3）第i个人拿走石子的最后一堆，标记为当前位置p_i。第i+1个人将从p_i+堆开始拿取个。

4）如果某堆石子已被取完，该堆石子数为0，则在按逆时针顺序计数堆数时，不计入该堆。

请问最后一个被取走的石子，在哪一堆？

注意：有可能执行完M条指令后，石子没有被拿完；也有可能M条指令还没执行完，全部石子已经被拿空。无论哪一种情况，你都给出被拿走的最后一个石子所在堆的编号即可。

第一行输入两个数N和M。

第二行包含N个正整数，表示a_1,a_2,...,a_N,数字之间用空格隔开。

第三行到第M+2行，每行为两个正整数，表示每个人拿石头的指示d_i和x_i。

输出一行一个整数，表示最后一个被取走的石子所在的堆的编号。

【样例1解释】

根据第一个人拿石子的指令，他将拿走第1堆（从第1堆往后循环数4，还是回到第1堆）的2个。剩余的石子为0 1 6 5.

第二个人的当前位置为1，往后数3，到达第4堆。取走5个石子后，剩余石子为0 1 6 0。

第三个人的当前位置为4。往后数2，因为第1堆石子为0，不计数，所以到达第3堆。取走3个之后，剩余石子为0 1 3 0.

第四个人的当前位置为3。往后数2，因为第4堆和第1堆石子均为0，不计数，所以到达第3堆。第3堆不够取，依次往后从第4堆、第1堆、第2堆取，已经全部取完石子，依然凑不够所需要的6个石子。

最后一个被取走的石子在第2堆，输出2.

【数据范围】

对于30%的数据, 0< M\le N\le 100,0< a_i \le 100。

对于100%的数据,0< M\le N\le 10^4,0< a_i \le 10^4。

云南编程挑战赛