問題文

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

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

風が吹くと，雪玉は風と同じ向きに，風の強さと同じ距離だけ転がる．すなわち $j$ 日目 ($1 \leq j \leq 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 \leq i \leq N$) には $Q$ 日目の終わりにおける，雪玉 $i$ の重さを出力せよ．

4 3
-2 3 5 8
2
-4
7

5
4
2
6

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

3000000000000

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

14
8
7
9
11
10
9
8
5
10

制約

• $1 \leq N \leq 2 \times 10^5$．
• $1 \leq Q \leq 2 \times 10^5$．
• $|X_i| \leq 10^{12}$ ($1 \leq i \leq N$)．
• $X_i \leq X_{i+1}$ ($1 \leq i \leq N-1$)．
• $|W_j| \leq 10^{12}$ ($1 \leq j \leq Q$)．

小課題

1. ($33$ 点) $N \leq 2000$, $Q \leq 2000$．
2. ($67$ 点)追加の制約はない．