小明每天都会读书，并且他可能会把一本书读很多遍。书架上有$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$。