JOI 平原是一片从西向东延伸的广阔平原。我们可以将 JOI 平原视为一条数轴。JOI 平原上的一个点由坐标表示。数轴的正方向对应东方。现在 JOI 平原迎来了冬天。平原上有 $N$ 个雪球，从西向东依次编号为 $1$ 到 $N$。起初，第 $i$ 个雪球（$1 \le i \le N$）的坐标为整数 $X_i$。

冬季的 JOI 平原上会刮起强风。你有 $Q$ 天的风力观测数据。在第 $j$ 天（$1 \le j \le Q$），风由一个整数 $W_j$ 描述。如果 $W_j$ 为负，则风向为西；如果 $W_j$ 非负，则风向为东。风力强度为 $|W_j|$。

当风吹起时，雪球会向风吹的方向移动，移动距离等于风力强度。换句话说，如果第 $j$ 天（$1 \le j \le Q$）开始时某个雪球位于坐标 $x$，则该雪球会从坐标 $x$ 移动到坐标 $x + W_j$。在第 $j$ 天结束时，雪球的坐标变为 $x + W_j$。注意，每天所有雪球同时移动，且速度相同。

起初，JOI 平原覆盖着积雪。如果雪球移动经过的区间覆盖有积雪，则雪球会收集积雪，雪球的重量增加，且该区间上的积雪消失。换句话说，对于整数 $a$，假设从 $a$ 到 $a + 1$ 的区间覆盖有积雪。如果雪球移动经过该区间，则雪球的重量增加 $1$，且从 $a$ 到 $a + 1$ 区间的积雪消失。然而，如果雪球移动经过的区间没有积雪，则雪球的重量保持不变。

起初，每个雪球的重量均为 $0$。在 $Q$ 天的观测数据中，并没有下雪。

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

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

输入格式

从标准输入读取以下数据。给定值均为整数。

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

输出格式

向标准输出打印 $N$ 行。第 $i$ 行（$1 \le i \le N$）应包含第 $Q$ 天结束时第 $i$ 个雪球的重量。

数据范围

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

子任务

1. (33 分) $N \le 2\,000, Q \le 2\,000$
2. (67 分) 无附加限制

样例

样例输入 1

4 3
-2 3 5 8
2
-4
7

样例输出 1

5
4
2
6

说明 1

在此样例输入中，每个雪球的重量变化如下： 起初，雪球从西向东的坐标分别为 $-2, 3, 5, 8$。雪球的重量分别为 $0, 0, 0, 0$。 第一天，风向为东，强度为 $2$。第一天结束时，雪球的坐标为 $0, 5, 7, 10$。雪球的重量分别为 $2, 2, 2, 2$。 第二天，风向为西，强度为 $4$。第二天结束时，雪球的坐标为 $-4, 1, 3, 6$。雪球的重量分别为 $4, 4, 2, 3$。 第三天，风向为东，强度为 $7$。第三天结束时，雪球的坐标为 $3, 8, 10, 13$。雪球的重量分别为 $5, 4, 2, 6$。

因此输出 $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