Background

战列巡洋舰战术折跃到了虫族老巢的上方，虫族喜欢将基地建成长条形，现在虫族已经发现了战列巡洋舰，战列巡洋舰指挥官估计现在可以打出m次大和炮，因为有虫族干扰，所以可能不能发挥最大威力，但是指挥官知道至少可以对x长度的区间造成伤害。因为建筑构造不同，重要性不同，所以大和炮击中产生的价值也不一样，定义大和炮产生的价值为造成伤害区间的价值之和。现在指挥官想知道对于每一发大和炮的最大价值是多少，好汇报给后面赶来的刘宝宝军团。因为指挥官忙着指挥，所以他把任务交给了你。

Description

给定一个长度为 \(n\) 的虫族老巢 \(A\) 。

定义 \(f(l,r)=\sum_{i=l}^{r} A_{i}\)。

发射 \(m\) 颗大和炮，每一颗一个数字 \(x\)，请求出所有满足 \(r-l+1 \ge x\) 区间 \([l,r]\) 中最大的 \(f(l,r)\)。

Format

Input

第一行两个数，表示 \(n\) 和 \(m\) 。
之后 \(n\) 个数，表示虫族老巢 \(A\)。
之后 \(m\) 行每行一个数 \(x\)，表示 \(x\) 。

Output

输出 \(m\) 行，每行一个答案，表示最大的 \(f(l,r)\)。

Sample 1

Input

5 5
1 2 3 4 5
1
2
3
4
5

Output

15
15
15
15
15

Limitation

\(1 \le n \le 10^4,0 \le m \le 10^5,|A_i| \le 10^4\)
注意， \(A_i\)可能为负数