小明每天都会读书,并且他可能会把一本书读很多遍。书架上有m本书,每本书的编号为1~m,每本书有x[i]页。现在知道小明从明天开始的n天读书计划:每天只会阅读一本书,书的编号为A[i],这一天会读B[i]页,并且每次读会接着上次读这本书的地方继续读下去。如果读到书本的最后了,就会从头重新阅读。现在小明想知道每本书他是在第几天第一次读完?
数据输入
第一行两个数字m和n,含义如上。
第二行是m个数字表示每本书的页数。
第三行到第n+2行,第p行含有两个数字A[i]和B[i]分别表示第p−2天阅读的书籍编号和页数。
数据输出
输出一行n个数字,分别表示每本书第一次读完是第几天。如果某本书n天之后,一遍都没读完,相应位置就输出-1。数字之间用一个空格隔开,行末无空格。
样例输入
4 5
1 2 3 4
2 1
1 1
3 4
2 1
1 3
样例输出
2 4 3 -1
范围说明
- 对于50%的数据:1leqn,m,x[i],A[i],B[i]leq1000;
- 对于100%的数据:1leqn,m,x[i],A[i],B[i]leq105。