[AdditionalFile4184.zip](file://AdditionalFile4184.zip?type=additional_file)

#4184. 「ROI 2024 Day2」无人机比赛

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI 2024 Day2 T3. Гонка дронов

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

共有 $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$ 是样例。