Problem Description

On an infinite number line, there are $N$ snowballs numbered from $1$ to $N$. The $i$-th snowball is initially at position $A_i$. Initially, the entire number line is covered with snow. Over the next $Q$ days, strong winds will blow, with the wind strength on the $j$-th day being $W_j$. If $W_j$ is positive, all snowballs will move $W_j$ units to the right; if $W_j$ is negative, all snowballs will move $-W_j$ units to the left.

When a snowball rolls over a snow-covered interval $[a, a+1]$, its mass increases by one, and the snow in that interval is cleared. Initially, all snowballs have a mass of $0$, and no new snow falls during these $Q$ days.

You are to determine the mass of each snowball after these $Q$ days.

Input Format

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

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 for each day.

Output Format

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

Sample Input and Output

Input Sample #1

4 3
-2 3 5 8
2
-4
7

Output Sample #1

5
4
2
6

Input Sample #2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

Output Sample #2

3000000000000

Input Sample #3

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

Output Sample #3

14
8
7
9
11
10
9
8
5
10

Notes

Sample 1 Explanation

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

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

Data Constraints

This problem uses batched testing.

• Subtask 1 (33 points): $N, Q \le 2000$.
• Subtask 2 (67 points): No additional constraints.

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

Notes

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

见题面 Input 部分

见题面 Output 部分