雪玉 (Snowball)

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

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

風が吹くと，雪玉は風と同じ向きに，風の強さと同じ距離だけ転がる．すなわち \(j\) 日目 (\(1 \leqq j \leqq 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\) \(\cdots\) \(X_N\)
\(W_1\)
\(\vdots\)
\(W_Q\)

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

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

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

JOI 2021 · JCIOI · CC BY-SA 4.0