Description

On an infinitely long number line, there are $N$ snowballs, numbered $1 \sim N$. The $i$-th snowball is at point $A_i$. At the beginning, the entire number line is fully covered with snow. Then, over the next $Q$ days, strong winds will blow. The wind strength on day $j$ is $W_j$. If $W_j$ is positive, all snowballs move to the right by $W_j$ units. If $W_j$ is negative, all snowballs move to the left by $-W_j$ units.

When an interval $[a,a+1]$ is covered with snow, a snowball’s mass increases by $1$ when it rolls over that interval, and the snow in that interval is cleared. Initially, every snowball has mass $0$, and during these $Q$ days, no new snow falls.

You want to know the mass of each snowball after these $Q$ days end.

Input Format

The first line contains two integers $N, Q$, representing the number of snowballs and the number of days with wind.

The second line contains $N$ integers $A_i$, representing the initial positions of the $N$ snowballs.

The next $Q$ lines each contain one integer $W_j$, representing the wind strength of each day.

Output Format

Output $N$ lines, each containing one integer, representing the mass of each snowball after the $Q$ days.

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

Hint

Explanation of Sample 1

The initial positions of the snowballs are $-2, 3, 5, 8$, and the initial masses are $0, 0, 0, 0$.

• After the first day, the snowballs are at positions $0, 5, 7, 10$, with masses $2, 2, 2, 2$.
• After the second day, the snowballs are at positions $-4, 1, 3, 6$, with masses $4, 4, 2, 3$.
• After the third day, the snowballs are at positions $3, 8, 10, 13$, with masses $5, 4, 2, 6$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (33 pts): $N, Q \le 2000$.
• Subtask 2 (67 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le N, Q \le 2 \times 10^5$, $|A_i|, |W_j| \le 10^{12}$, $A_i < A_{i+1}$.

Note

Translated from The 20th Japanese Olympiad in Informatics Final Round B English translation Snowball.

Translated by ChatGPT 5