あなたが耕作している農地は、西から東へ並んだいくつかの区画で構成されています。現在、各区画には一定量の小麦が植えられており、その量は区画によって異なる場合があります。すべての小麦は、ある日数が経過すると収穫可能になります。

あなたが直面している大きな問題は、毎晩西からやってくる飢えたイノシシです。どの区画にも小麦が残っていない場合、イノシシはそのまま引き返します。そうでない場合、イノシシは小麦が残っている最も西の区画へ向かい、そこで小麦を1単位食べます。その後、イノシシは東隣の区画へ移動して小麦を1単位食べるという行動を、小麦が残っていない区画に遭遇するか、最も東の区画で食べ終えるまで続け、そこで家へ帰ります。

被害を軽減するために、あなたは今日、いくつかの区画（ゼロ個でもよい）を選んで、それらの区画からすべての小麦を取り除くことを計画しています。これにより、その後の数日間でイノシシが食べる小麦の量を減らし、イノシシが帰るように仕向けます。その後、イノシシは毎晩やってきますが、被害をさらに軽減するためにあなたができることはありません。

収穫可能な候補日が1つ以上与えられます。各候補日について、最適に選んだ区画から小麦を取り除いたと仮定したときに、その日に残っている小麦の最大量を求めてください。区画の最適な選択は、候補日ごとに異なる場合があります。

入力

入力は以下の形式の単一のテストケースで構成されます。

$n$ $m$ $a_1 \dots a_n$ $d_1$ $\vdots$ $d_m$

整数 $n$ は区画の数です ($2 \le n \le 2 \times 10^5$)。区画には西から東へ 1 から $n$ までの番号が付けられています。整数 $m$ は収穫候補日の数です ($1 \le m \le 2 \times 10^5$)。各 $i = 1, \dots, n$ について、整数 $a_i$ は区画 $i$ にある小麦の単位数です ($0 \le a_i \le 10^{12}$)。各 $j = 1, \dots, m$ について、整数 $d_j$ は $j$ 番目の収穫候補日までの日数です ($1 \le d_j \le 2 \times 10^{17}$)。つまり、その日までにイノシシは $d_j$ 回やってきます。

出力

$m$ 行を出力してください。$j$ 行目には、$j$ 番目の収穫候補日に残っている小麦の最大単位数を表す整数を記述してください。

入出力例

入力 1

3 4
3 1 4
1
2
3
7

出力 1

6
5
4
0

注記 1

サンプル入力 1 において、小麦を何も取り除かない場合、各区画の小麦の量は次のように変化します。 $(3, 1, 4) \to (2, 0, 3) \to (1, 0, 3) \to (0, 0, 3) \to (0, 0, 2) \to (0, 0, 1) \to (0, 0, 0)$

代わりに、区画 2 の小麦を取り除いた場合、量は次のように変化します。 $(3, 0, 4) \to (2, 0, 4) \to (1, 0, 4) \to (0, 0, 4) \to (0, 0, 3) \to (0, 0, 2) \to (0, 0, 1) \to (0, 0, 0)$

この選択は、与えられたすべての候補日に対して最適です。

入力 2

6 3
300 200 100 100 200 300
10
50
340

出力 2

1140
1000
560

注記 2

サンプル入力 2 において、最適な選択は以下の通りです。

• 1 番目の候補日については、何も取り除かないのが最適です。残りの量は $(290, 190, 90, 90, 190, 290)$ となります。
• 2 番目の候補日については、区画 3 の小麦を取り除くのが最適です。残りの量は $(250, 150, 0, 100, 200, 300)$ となります。
• 3 番目の候補日については、区画 2 と 4 の小麦を取り除くのが最適です。残りの量は $(0, 0, 60, 0, 200, 300)$ となります。

図 1. イノシシ