Problem Description

The JOI Plain is a very large plain that stretches in the east-west direction. This plain can be considered as a number line, and each location is represented by coordinates with the east direction being positive. The JOI Plain is entering winter, and $ N $ snowballs have been created at different coordinates. The snowballs are numbered from 1 to $ N $ from west to east. Initially, the coordinate of the snowball $ i $ ($1 \leq i \leq N$) is the integer $ X_i $.

The JOI Plain is also known for its strong winds during winter. You have obtained wind observation data for $ Q $ days. The data for the $ j $-th day ($1 \leq j \leq Q$) is represented by the integer $ W_j $. When $ W_j $ is negative, it means the wind blows westward with a strength of $ |W_j |$; when $ W_j $ is non-negative, it means the wind blows eastward with a strength of $ W_j $.

When the wind blows, the snowballs roll in the same direction as the wind, covering the same distance as the wind's strength. That is, if a snowball is at coordinate $ x $ at the beginning of the $ j $-th day ($1 \leq j \leq Q$), it will roll from coordinate $ x $ to coordinate $ x + W_j $. By the end of the $ j $-th day, the coordinate of that snowball will be $ x + W_j $. Note that all snowballs roll simultaneously and at the same speed each day.

Initially, the entire JOI Plain was covered with snow. When a snowball rolls over a range where snow is accumulated, the snow sticks to the snowball, increasing its weight, and the snow in that range disappears. That is, let $ a $ be an integer, and suppose there is snow remaining in the range from coordinate $ a $ to coordinate $ a + 1 $. When a snowball rolls over this range, its weight increases by 1, and the snow in the range from coordinate $ a $ to coordinate $ a + 1 $ disappears. However, if a snowball rolls over a range where there is no snow, its weight does not change.

Initially, the weight of all snowballs is 0. Also, no new snow fell during the observed $ Q $ days.

You want to know the weight of each snowball at the end of the $ Q $-th day.

Given the initial coordinates of the snowballs and the wind observation data for $ Q $ days, create a program to determine the weight of each snowball at the end of the $ Q $-th day.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ N $ $ Q $ $ X_1 $ $\cdots$ $ X_N $ $ W_1 $ $\vdots$ $ W_Q $

Output Format

Output $ N $ lines to the standard output. The $ i $-th line ($1 \leq i \leq N$) should contain the weight of the snowball $ i $ at the end of the $ Q $-th day.

Sample Input and Output

Sample Input #1

4 3
-2 3 5 8
2
-4
7

Sample Output #1

5
4
2
6

Sample Input #2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

Sample Output #2

3000000000000

Sample Input #3

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

Sample Output #3

14
8
7
9
11
10
9
8
5
10

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq Q \leq 200,000$.
• $|X_i| \leq 1,000,000,000,000 (= 10^{12})$ ($1 \leq i \leq N$).
• $ X_i < X_{i + 1} $ ($1 \leq i \leq N - 1$).
• $|W_j| \leq 1,000,000,000,000 (= 10^{12})$ ($1 \leq j \leq Q$).

Subtasks

1. ($ 33 $ points) $N \leq 2,000$, $Q \leq 2,000$.
2. ($ 67 $ points) No additional constraints.

Sample Explanation 1

In this input example, the coordinates and weights of the snowballs change as follows:
- Initially, the coordinates of the snowballs are, in order from snowball 1, $ -2, 3, 5, 8 $. The weights of the snowballs are, in order from snowball 1, $ 0, 0, 0, 0 $.
- On the 1st day, the wind blows eastward with a strength of 2. By the end of the 1st day, the coordinates of the snowballs are, in order from snowball 1, $ 0, 5, 7, 10 $. The weights of the snowballs are, in order from snowball 1, $ 2, 2, 2, 2 $.
- On the 2nd day, the wind blows westward with a strength of 4. By the end of the 2nd day, the coordinates of the snowballs are, in order from snowball 1, $ -4, 1, 3, 6 $. The weights of the snowballs are, in order from snowball 1, $ 4, 4, 2, 3 $.
- On the 3rd day, the wind blows eastward with a strength of 7. By the end of the 3rd day, the coordinates of the snowballs are, in order from snowball 1, $ 3, 8, 10, 13 $. The weights of the snowballs are, in order from snowball 1, $ 5, 4, 2, 6 $.
Therefore, output the weights of the snowballs, $ 5, 4, 2, 6 $, in order.

Sample Explanation 2

见题面 Input 部分

见题面 Output 部分