UOJ Logo

NOI.AC

1S 512MB

#1605. 爱看书的小明

Statistics

小明每天都会读书,并且他可能会把一本书读很多遍。书架上有$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%的数据:$1leq n, m, x[i], A[i], B[i]leq 1000$;
  • 对于100%的数据:$1leq n, m, x[i], A[i], B[i] leq 10^5$。