Description

The JOI plain is a wide plain spreading from west to east. We can consider the JOI plain as a number line. A spot on the JOI plain is denoted by a coordinate. The positive direction of the number line corresponds to the east direction. Now winter comes in the JOI plain. There are $N$ snowballs on it, numbered from $1$ to $N$ from the west to the east. In the beginning, the coordinate of the snowball $i$ ($1 \leq i \leq N$) is an integer $X_i$.

Strong wind blows in the JOI plain in winter. You have observation data of wind for $Q$ days. On the $j$-th day ($1 \leq j \leq Q$), the wind is described by an integer $W_j$. If $W_j$ is negative, then the wind blows to the west direction. If $W_j$ is not negative, then the wind blows to the east direction. The strength of the wind is $|W_j|$.

When wind blows, a snowball is moved to the same direction as the wind, and its length of move is equal to the strength of the wind. In other words, if there is a snowball in the coordinate $x$ in the beginning of the $j$-th day ($1 \leq j \leq Q$), then the snowball is moved from the coordinate $x$ to the coordinate $x + W_j$. At the end of the j-th day, the coordinate of the snowball becomes $x + W_j$. Note that, in each day, the snowballs are moved at the same time, and their speeds are the same.

Initially, the JOI plain is covered with snow. If a snowball is moved on an interval covered with snow, then the snowball accumulates the snow, the weight of the snowball is increased, and the snow on the interval disappears. In other words, for an integer $a$, assume that the interval from $a$ to $a + 1$ is covered with snow. If a snowball is moved on this interval, then the weight of the snowball is increased by $1$, and the snow on the interval from $a$ to $a + 1$ disappears. However, if a snowball is moved on an interval without snow, the weight of the snowball remains the same.

Initially, the weight of every snowball is $0$. It did not snow on the $Q$ days of observation data.

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

Write a program which, given the initial position of each snowball and observation data of wind for $Q$ days, calculates the weight of each snowball at the end of the $Q$-th day.

Input

Read the following data from the standard input. Given values are all integers.

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

Output

Write $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 1

4 3
-2 3 5 8
2
-4
7

5
4
2
6

In this sample input, the weight of each snowball varies as follows.

• Initially, the coordinates of the snowballs are $−2, 3, 5, 8$ from the west to the east. The weights of the snowballs are $0, 0, 0, 0$, respectively.
• On the first day, wind blows to the east direction, and its strength is $2$. At the end of the first day, the coordinates of the snowballs are $0, 5, 7, 10$. The weights of the snowballs are $2, 2, 2, 2$, respectively.
• On the second day, wind blows to the west direction, and its strength is $4$. At the end of the second day, the coordinates of the snowballs are $−4, 1, 3, 6$. The weights of the snowballs are $4, 4, 2, 3$, respectively.
• On the third day, wind blows to the east direction, and its strength is $7$. At the end of the third day, the coordinates of the snowballs are $3, 8, 10, 13$. The weights of the snowballs are $5, 4, 2, 6$, respectively.

Hence output $5, 4, 2, 6$, which are the weights of the snowballs at the end of the third day.

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

Constraints

• $1 \leq N \leq 2 \times 10^5$.
• $1 \leq Q \leq 2 \times 10^5$.
• $|X_i| \leq 10^{12}$ ($1 \leq i \leq N$).
• $X_i \leq X_{i+1}$ ($1 \leq i \leq N-1$).
• $|W_j| \leq 10^{12}$ ($1 \leq j \leq Q$).

Subtasks

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