9151 - 取石子(stone)

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

现在有M个人来拿取石子,每个人取走石子的指令包含两个数,d_ix_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条指令还没执行完,全部石子已经被拿空。无论哪一种情况,你都给出被拿走的最后一个石子所在堆的编号即可。

输入

第一行输入两个数NM

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

第三行到第M+2行,每行为两个正整数,表示每个人拿石头的指示d_ix_i

输出

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

样例

输入

4 4
2 1 6 5
4 2
3 5
2 3
2 6

输出

2

输入

5 4
7 2 6 7 3
2 9
2 2
10 7
2 1

输出

2

提示

【样例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

来源

云南编程挑战赛

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题