You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

$\sigma = \Sigma = \sum$。（$\sigma = \Sigma = \sum$)

Description

给定一个长度为 $n$ 的序列 $A$ 。

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

询问 $m$ 次，每次询问一个数字 $x$，请求出所有满足 $r-l+1 \ge x$ 区间 $[l,r]$ 中最大的 $f(l,r)$。

Input

第一行两个数，表示 $n$ 和 $m$ 。

• 之后 $n$ 个数，表示序列 $A$。
• 之后 $m$ 行每行一个数 $x$，表示一次询问。

outpuT

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

Samples

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

15
15
15
15
15

Limitation

• 对于 $30\%$ 的数据， $1\le n,m\le 5$。
• 对于 $20\%$ 的数据，$A_i=0$;
• 对于另外 $10\%$ 的数据，$A_i> 0$
• 对于另外 $10\%$ 的数据，$A_i< 0$。
• 对于 $100\%$ 的数据，$1 \leq x \leq n \leq 10^{4} ,0 \leq m \leq 10^{5} , |A_i| \leq 10^{4},-2^{63}\le \sum_{i=1}^n A_i < 2^{63}$。