H. 打饭
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

再晚一秒就饿4了。

小A来到桃园餐厅就餐。桃园食堂的窗口可以视为在一条直线上，第 $$$i$$$ 个窗口的位置距出发点距离为 $$$i$$$ 个单位。小A从位置 $$$0$$$ 出发去打饭。小A可以在不超出窗口范围的前提下任意左右移动。在第 $$$i$$$ 个窗口，如果他没在这个窗口打过饭，则他可以向餐盘加入 $$$a_i$$$ 克食物（不可少打）。当他移动一个单位时，需要消耗 $$$w+1$$$ 单位能量，其中 $$$w$$$ 为他的餐盘上当前的食物重量总和。

现在他打算从起点出发，尽可能多的多打饭并回到起点。已知他的初始能量为 $$$x$$$,请问他最多能打多少克食物(没出发过也算一种方案)。因为每一天小A的初始能量不一样，所以他会对你进行多次询问。

Input

第一行两个整数 $$$n,q(1\le n \le 10^5;1\le q \le 10^5)$$$，代表窗口数和询问的次数。

第二行 $$$n$$$ 个整数 $$$a_1,a_2...a_n(1\le a_i \le 10^6)$$$，代表第 $$$i$$$ 个窗口可以打的食物量。

接下来连续的 $$$q$$$ 行，每行一个整数 $$$x(1\le x \le 10^6)$$$，第 $$$i$$$ 行代表小A第 $$$i$$$ 天的初始能量。

Output

共 $$$q$$$ 行，每行一个整数，代表第 $$$i$$$ 天小A最多能打多少克的食物。

Example
Input
5 4
2 1 3 4 1
100
17
5
3
Output
11
5
2
0