题目描述

给出n个数$a_{1}$,$a_{2}$,⋯,$a_n$，和一个空的数列b。对于$i=1$∼n，进行以下操作：

• 将1,2,3,⋯,$a_i$按从小到大的顺序依次添加到b的尾部。

所有操作完成后，你需要回答Q个询问，每个询问包含1个正整数s，你要输出满足以下条件的最小正整数m的值：$\sum_{i=1}^{m}b_i\ge S$

如果没有满足条件的m，输出−1。

输入格式

第1行，2个正整数n,Q

第2行，n个正整数$a_{1}$,$a_{2}$,⋯,$a_n$

第3∼Q+2行，每行1个整数，表示一个询问

输出格式

输出Q行，对每个询问，用一行输出答案。

4 3
1 2 3 4
4
10
25

3
6
-1

提示

第一次操作$a_{1}=1$，数列$b=[1]$；第二次操作$a_{2}=2$，数列$b=[1,1,2]$；第三次操作$a_{3}=3$，数列$b=[1,1,2,1,2,3]$；第四次操作$a_{4}=4$，数列$b=[1,1,2,1,2,3,1,2,3,4]$。

对第1个询问$S=3$：前3个数$1+1+2=4\ge S$，所以$m=3$是满足条件的最小值。

对第2个询问$S=10$：前6个数$1+1+2+1+2+3=10\ge S$，所以$m=6$是满足条件的最小值。

对第3个询问$S=25$：b数列所有数总和$20\lt S$，所以没有满足条件的m。

1 1
1
1

1

1 1  
1  
1

1

5 3
1000000 1000000 1000000 1000000 1000000
1
100000000000
200000000000

1
447214
632456

数据范围

前50%数据：$1\le Q\le 100$；

前70%数据：所有$a_i$的总和不超过$10^{5}$。

100%数据：

$1\le n\le 10^{5}$；$1\le Q\le 10^{5}$；

$1\le a_i\le 10^{6}$；$1\le S\le 10^{18}$。