区间最大和

给定一个长度为 $N$ 的数列 $A$，然后进行若干次询问。每次给定一个整数 $T$，求出最大的 $k$，满足

你的算法必须是在线的（必须即时回答每一个询问，不能等待收到所有询问后再统一处理）。数据保证 $0 \leqslant T \leqslant \sum_{i=1}^{N} A[i]$。

约定：$k$ 可以等于 $0$，此时认为 $\sum_{i=1}^{0} A[i] = 0$。

输入格式

第一行包含两个整数 $N,Q$，分别表示数列的长度和询问次数。

第二行包含 $N$ 个正整数，表示数列 $A_1, A_2, \dots, A_N$。

接下来 $Q$ 行，每行一个整数 $T$，表示一次询问。

输出格式

对于每次询问输出一行一个整数，表示最大的 $k$。

数据范围

$1 \leqslant N \leqslant 10^5$,
$1 \leqslant Q \leqslant 10^5$,
$1 \leqslant A[i] \leqslant 10^9$,
$0 \leqslant T \leqslant \sum_{i=1}^{N} A[i]$

输入样例：

5 4
1 2 3 4 5
0
6
8
15

输出样例：

0
3
3
5

来源

• 《算法竞赛进阶指南》0x06 倍增