JOI 平原问题

JOI 平原是一个东西向延伸的非常大的平原。可以将该平原视为数轴，并使用以东为正方向的坐标表示各个地点。JOI 平原在冬季迎来了 $N$ 个雪球，每个雪球被放置在不同的坐标上。雪球按照从西到东的顺序依次编号为 $1$ 到 $N$。最初，雪球 $i$（$1 \leq i \leq N$）的坐标为整数 $X_i$。

此外，JOI 平原以强风而闻名。你获得了连续 $Q$ 天的风速观测数据。第 $j$ 天（$1 \leq j \leq Q$）的风数据用整数 $W_j$ 表示。当 $W_j$ 为负数时，表示风向向西；当 $W_j$ 不为负数时，表示风向向东，并且风速为 $|W_j|$。

当风吹动时，雪球会朝着与风相同的方向滚动，滚动的距离与风速相等。也就是说，在第 $j$ 天（$1 \leq j \leq Q$）开始时，如果坐标 $x$ 上有一个雪球，那么这个雪球会滚动到坐标 $x + W_j$。在第 $j$ 天结束时，该雪球的坐标将变为 $x + W_j$。然而需要注意的是，每一天所有的雪球都会同时以相同的速度滚动。

最初，整个 JOI 平原上覆盖着一层雪。当雪球滚动经过一处覆盖有雪的区域时，雪球会吸附雪并增加重量，并且该区域的雪会消失。也就是说，假设整数 $a$ 表示某个区间的起点坐标，而 $a + 1$ 表示该区间的终点坐标。如果区间 $[a, a + 1]$ 上仍存在雪，当雪球滚动经过该区间时，该雪球的重量会增加 $1$，同时该区间的雪会消失。然而，如果雪已经消失，那么雪球的重量不会改变。

最初，所有的雪球的重量都为 $0$。另外，观测期间的 $Q$ 天中没有下雪。

你想知道第 $Q$ 天结束时各个雪球的重量。

给定雪球的初始坐标和 $Q$ 天的风速观测数据，请编写一个程序来计算第 $Q$ 天结束时每个雪球的重量。

输入

输入从标准输入读取，具体格式如下所示。所有输入值都是整数。

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

输出

输出到标准输出，共 $N$ 行。第 $i$ 行（$1 \leq i \leq N$）输出第 $Q$ 天结束时雪球 $i$ 的重量。

约束条件

• $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$)。

子任务

1. （33 分）$N \leq 2,000$，$Q \leq 2,000$。
2. （67 分）无额外的限制。

示例 1

4 3
-2 3 5 8
2
-4
7

输出示例 1

5
4
2
6

在这个示例中，每个雪球的坐标和重量的变化如下：

• 最初，每个雪球的坐标和重量依次为 $-2, 3, 5, 8$ 和 $0, 0, 0, 0$。
• 第 1 天，东风强度为 2。第 1 天结束时，每个雪球的坐标和重量分别为 $0, 5, 7, 10$ 和 $2, 2, 2, 2$。
• 第 2 天，西风强度为 4。第 2 天结束时，每个雪球的坐标和重量分别为 $-4, 1, 3, 6$ 和 $4, 4, 2, 3$。
• 第 3 天，东风强度为 7。第 3 天结束时，每个雪球的坐标和重量分别为 $3, 8, 10, 13$ 和 $5, 4, 2, 6$。

因此，在第 3 天结束时，各个雪球的重量分别为 $5, 4, 2, 6$。

示例 2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

输出示例 2

3000000000000

示例 3

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

输出示例 3

14
8
7
9
11
10
9
8
5
10