题目描述

给定一个序列 $a_{1}$，$a_{2}$……$a_{n}$ 和$m$个询问。 每次询问给出两个数$l,x$，求最大的$r(r \le n)$满足$a_{l}$+$a_{l+1}+$……$+a_r \le x$。 如果不存在这样的$r$，即$a_{l}>x$，输出$-1$。

输入格式

第一行两个整数$n$和$m$。 第二行$n$个整数，表示$a_{1}$，$a_{2}$……$a_{n}$。 接下来有$m$行，每行两个整数$l,x$。

输出格式

输出$m$行，每行一个整数表示答案。

样例 #1

样例输入 #1

5 5
1 1 5 3 5
2 8
3 16
3 6
5 4
1 3

样例输出 #1

3
5
3
-1
2

提示

对于$100$的数据，满足$1\le n,m\le 10^5,1 \le l \le n,1 \le a_{i} \le 10^9,1 \le x \le 10^{14}$。