Snowball Rolling on a Snow‐Covered Number Line

An infinite number line is initially covered with snow. There are N snowballs numbered from 1 to N, and the i-th snowball is initially located at position \(A_i\). Each snowball starts with mass 0.

For Q days, a strong wind occurs. On day \(j\) the wind strength is \(W_j\). If \(W_j>0\), every snowball moves \(W_j\) units to the right; if \(W_j<0\), every snowball moves \(-W_j\) units to the left. When a snowball rolls over an interval \([a, a+1]\) that is still covered with snow, its mass increases by 1 and the snow on that interval is cleared (i.e. each interval can contribute at most once overall).

After all Q days the task is to determine the final mass for each snowball. Note that the movement is continuous and all snowballs move simultaneously. In the case of a positive wind, the ball that is further to the left will reach an interval first; for a negative wind, the ball that is further to the right will reach an interval first.

It is guaranteed that the overall range of positions touched by any snowball is limited. In other words, if we define the prefix sum \(S_k = \sum_{j=1}^{k}W_j\) (with \(S_0=0\)), then the positions visited by any snowball lie in the range \([\min_{0\le k\le Q}(A_i+S_k), \max_{0\le k\le Q}(A_i+S_k)]\). This allows simulation using proper coordinate compression.

inputFormat

The first line contains two integers \(N\) and \(Q\) (\(1 \le N, Q \le 1000\)).

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\), representing the initial positions of the snowballs.

The third line contains \(Q\) integers \(W_1, W_2, \dots, W_Q\) (with \(|W_j| \le 1000\)), the wind strengths for each day.

outputFormat

Output one line containing \(N\) integers. The \(i\)-th integer is the final mass of the snowball numbered \(i\) after \(Q\) days.

sample

3 2
1 2 3
1 1

1 1 2