题目描述

因诺波利斯市正在举办无人机比赛。

共有 $n$ 架无人机参赛，第 $i$ 架无人机飞行一单位距离需要 $t_i$ 秒。比赛在一条直线上进行，设有 $m$ 个编号从 $1$ 到 $m$ 的门，第 $i$ 个门位于起跑线起点的 $s_i$ 距离处。

比赛将由前 $k$ 架无人机参加，编号从 $1$ 到 $k$。赛前不久，裁判会宣布具体的 $k$ 值，因此你需要为所有从 $1$ 到 $n$ 的 $k$ 值分析比赛情况。

---

比赛规则

• 无人机从起点 $0$ 开始飞行。每架无人机有一个「存档点」——即最后一个它执行了「位置保存」的门。初始时，所有无人机的存档点都是起点 $0$。
• 无人机会从各自的存档点开始飞行，并继续前进，直到一个或多个无人机到达门的位置（可能不同的无人机到达不同的门）。此时，在所有到达门的无人机中，编号最小的无人机将其位置保存，即更新其存档点为当前位置。其他无人机则瞬间传送回它们的存档点。之后比赛继续以同样的方式进行。
• 一旦无人机的位置在最后一个门 $m$ 保存后，它就完成了赛程。尚未完成赛程的无人机会像往常一样传送回其存档点，比赛继续进行。当所有无人机都完成赛程后，比赛结束。

传送是一个非常耗能的过程。为了准备比赛，需要知道在比赛结束前，所有无人机总共需要进行多少次传送。记 $c_k$ 为当有前 $k$ 架无人机参加比赛时，所有无人机的总传送次数。求 $c_1, c_2, \ldots, c_n$ 的值。

---

输入格式

第一行给出两个整数 $n, m$ ($2 \le n \le 1.5\cdot 10^5$, $1 \le m \le 1.5\cdot 10^5$)，分别表示无人机的数量和门的数量。

第二行给出 $n$ 个正整数 $t_1, t_2, \ldots ,t_n$ ($1 \le t_i \le 10^9$)，其中 $t_i$ 表示第 $i$ 架无人机飞行一单位距离所需的秒数。

第三行给出 $m$ 个正整数 $s_1, s_2, \ldots , s_m$ ($1 \le s_1 < s_2 < \ldots < s_m \le 1.5\cdot 10^5$)，其中 $s_i$ 表示第 $i$ 个门的位置。

---

输出格式

输出 $n$ 个整数 $c_1, c_2, \ldots, c_n$，每个整数代表当有前 $k$ 架无人机参加时，所有无人机的总传送次数。

---

样例 1

输入

3 3
1 2 3
1 3 6

输出

0
4
11

解释
当 $k = 1$ 时，无需任何传送，因为只有一架无人机参加。
当 $k = 2$ 时，无人机按各自速度到达门的次序和位置保存操作导致传送发生。

当 $k = 3$ 时，比赛过程如下图所示。

---

样例 2

输入

3 3
3 2 1
1 3 6

输出

0
5
13

---

样例 3

输入

2 5
2 1
1 3 4 6 7

输出

0
6

---

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 0 是样例。

子任务	分值	$n$ 的限制	$m$ 的限制	$t_i, s_i$ 的限制	附加限制	依赖
1	5	$n = 2$	$m \le 50$
2	7	$n \le 50$				0,1
3	13	$n \le 1000$	$m \le 5$	$t_i, s_i \le 10^5$		0
4	9	$n \le 10^5$			$s_{i+1} - s_i = s_1$
5	8		$m \le 10^5$		所有 $t_i$ 相同
6	10	$n \le 100$				0,1,2
7	5	$n \le 10^5$	$m = 2$	$t_i \le 2, s_i \le 10^5$
8	7	$n \le 10^4$	$m \le 10^5$	$t_i, s_i \le 10^5$
9	6					0,1,2,3,6
10		$n \le 5 \times 10^4$				0,1,2,3,6,9
11	8	$n \le 10^5$				0,1,2,6,8,10
12						0,1-11
13		无附加限制				0,1-12