题目背景

翻译自 ROI 2024 D2T3。

有 $n$ 架无人机报名参加一个无人机比赛，第 $i$ 架无人机飞过一单位距离需要 $t_i$ 秒。

比赛在一条直线上进行，该直线上有 $m$ 个门，编号从 $1$ 到 $m$，第 $i$ 个门位于距离比赛起点 $s_i$ 的位置。

因为赛道大小的限制，第一场比赛只会有前 $k$ 架无人机参与，编号从 $1$ 到 $k$。$k$ 的值由裁判在比赛开始前宣布，因此此时你需要对 $k$ 从 $1$ 到 $n$ 的比赛情况进行分析。

比赛的进行方式如下：

无人机从 $0$ 号点开始向门移动，每架无人机的速度不同。每架无人机都有一个存档点，即最后一个它进行了存档操作的门。最初，每架无人机的存档点都是 $0$ 号点。

在比赛中，所有无人机从其存档点开始移动，直到有一架或多架无人机到达一个门（有可能是不同无人机同时到达不同的门）。此时，在所有到达门的无人机中，选择编号最小的无人机，对该无人机进行存档操作，将其存档点设置为当前的位置。其他无人机立即传送到其存档点。然后，比赛继续进行。

如果一架无人机在最后一个编号为 $m$ 的门上进行存档操作，那么它就完成了比赛。尚未完成的无人机将传送到其存档点继续比赛。当所有无人机都完赛时，比赛结束。

题目描述

传送是一个非常耗能的过程。为了准备比赛，你需要了解所有无人机在比赛结束之前一共将进行多少次传送。设 $c_k$ 表示当前 $k$ 架无人机参与比赛时，所有无人机的总传送次数，则你需要求出 $c_1, c_2, \dots, c_n$ 的值。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示无人机的数量和门的数量（$2 \leq n \leq 150000$，$1 \leq m \leq 150000$）。

第二行包含 $n$ 个正整数 $t_1, t_2, \dots, t_n$，$t_i$ 表示第 $i$ 架无人机飞过一单位距离所需的秒数（$1 \leq t_i \leq 10^9$）。

第三行包含 $m$ 个正整数 $s_1, s_2, \dots, s_m$，$s_i$ 表示第 $i$ 个门的位置（$1 \leq s_1 < s_2 < \dots < s_m \leq 150000$）。

输出格式

输出 $n$ 个整数 $c_1, c_2, \dots, c_n$，意义见题目描述。

3 3
1 2 3
1 3 6

0
4
11

3 3
3 2 1
1 3 6

0
5
13

2 5
2 1
1 3 4 6 7

0
6

提示

样例 $1$ 解释：

当 $k=1$，无需任何传送，因为只有一架无人机参加，只有它在一直存档。

当 $k=2$ 时，整个比赛的过程如下图所示。

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

各子任务特殊性质表格：