문제

JOI 平原は東西方向に広がるとても大きな平原である．この平原は数直線と見なすことができ，各地点は東向きを正とする座標であらわされる．JOI 平原は冬を迎え $N$ 個の雪玉が異なる座標に作られた．雪玉には西から順に $1$ から $N$ までの番号が付いている．最初，雪玉 $i$ ($1 \le i \le N$) の座標は整数 $X_i$ であった．

また JOI 平原は冬に強い風が吹くことで知られている．あなたは $Q$ 日間の風の観測データを入手した．$j$ 日目 ($1 \le j \le Q$) の風のデータは整数 $W_j$ であらわされる．$W_j$ が負のときは西向きに，$W_j$ が負でないときは東向きに，強さ $|W_j|$ の風が吹いたことを意味する．

風が吹くと，雪玉は風と同じ向きに，風の強さと同じ距離だけ転がる．すなわち $j$ 日目 ($1 \le j \le Q$) の始めに座標 $x$ に雪玉があったとき，その雪玉は座標 $x$ から座標 $x + W_j$ まで転がる．$j$ 日目の終わりには，その雪玉の座標は $x + W_j$ になる．ただし，各日においてすべての雪玉が同時に，同じ速さで転がる．

最初，JOI 平原全体に雪が積もっていた．雪が積もっている範囲を雪玉が転がると，雪が付着し，雪玉の重さが増え，その範囲の雪はなくなる．すなわち，$a$ を整数とし，座標 $a$ から座標 $a + 1$ までの範囲に雪が残っているとする．このとき，雪玉がこの範囲を転がると，その雪玉の重さが $1$ 増えて，座標 $a$ から座標 $a + 1$ までの範囲の雪がなくなる．ただし，雪が残っていない範囲を雪玉が転がったとしても，雪玉の重さは変わらない．

最初，すべての雪玉の重さは $0$ であった．また，観測した $Q$ 日間に新たに雪は降らなかった．

あなたは $Q$ 日目の終わりにおける雪玉の重さを知りたい．

雪玉の最初の座標，$Q$ 日間の風の観測データが与えられたとき，$Q$ 日目の終わりにおける，それぞれの雪玉の重さを求めるプログラムを作成せよ．

입력

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

$N$ $Q$
$X_1$ $\ldots$ $X_N$
$W_1$
$\vdots$
$W_Q$

출력

標準出力に $N$ 行で出力せよ．$i$ 行目 ($1 \le i \le N$) には $Q$ 日目の終わりにおける，雪玉 $i$ の重さを出力せよ．

예제 입력 1

4 3
-2 3 5 8
2
-4
7

예제 출력 1

5
4
2
6

예제 입력 2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

예제 출력 2

3000000000000

예제 입력 3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

예제 출력 3

14
8
7
9
11
10
9
8
5
10

제한

• $1 \le N \le 200\,000$．
• $1 \le Q \le 200\,000$．
• $|X_i| \le 1\,000\,000\,000\,000$ ($= 10^{12}$) ($1 \le i \le N$)．
• $X_i < X_{i+1}$ ($1 \le i \le N - 1$)．
• $|W_j| \le 1\,000\,000\,000\,000$ ($= 10^{12}$) ($1 \le j \le Q$)．

서브태스크

1. ($33$ 점) $N \le 2\,000$，$Q \le 2\,000$．
2. ($67$ 점) 追加の制約はない．