UOJ Logo

NOI.AC

1S 512MB

#1605. 爱看书的小明

统计

小明每天都会读书,并且他可能会把一本书读很多遍。书架上有m本书,每本书的编号为1~m,每本书有x[i]页。现在知道小明从明天开始的n天读书计划:每天只会阅读一本书,书的编号为A[i],这一天会读B[i]页,并且每次读会接着上次读这本书的地方继续读下去。如果读到书本的最后了,就会从头重新阅读。现在小明想知道每本书他是在第几天第一次读完?

数据输入

第一行两个数字mn,含义如上。

第二行是m个数字表示每本书的页数。

第三行到第n+2行,第p行含有两个数字A[i]B[i]分别表示第p2天阅读的书籍编号和页数。

数据输出

输出一行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