在因诺波利斯（Innopolis）举办了无人机竞速比赛。

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

比赛中将有编号为 $1$ 到 $k$ 的前 $k$ 架无人机参加。裁判会在比赛开始前立即宣布 $k$ 的值，因此你需要针对所有 $1 \le k \le n$ 的情况分析比赛。

比赛过程如下： 无人机从点 $0$ 出发向闸门方向移动，每架无人机都有各自的速度。每架无人机都有一个“恢复点”——即它最后一次成功保存位置的闸门。初始时，每架无人机的恢复点均为点 $0$。无人机每次都从各自的恢复点出发，继续移动，直到有一架或多架无人机到达某个闸门所在的位置（不同无人机可能到达不同的闸门）。此时，在所有到达了任意闸门的无人机中，选择编号最小的一架。该无人机保存当前位置，其恢复点更新为当前位置。其余无人机立即传送回各自的恢复点。之后，比赛以同样的方式继续进行。

一旦某架无人机在最后一个闸门（编号为 $m$）保存了位置，它就完成了比赛。尚未完成比赛的无人机像往常一样传送回各自的恢复点并继续比赛。当所有无人机都完成比赛时，比赛结束。

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

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 分别为无人机数量和闸门数量 ($2 \le n \le 150\,000, 1 \le m \le 150\,000$)。

第二行包含 $n$ 个正整数 $t_1, t_2, \dots, t_n$，其中 $t_i$ 为第 $i$ 架无人机飞行单位距离所需的时间 ($1 \le t_i \le 10^9$)。

第三行包含 $m$ 个正整数 $s_1, s_2, \dots, s_m$，其中 $s_i$ 为第 $i$ 个闸门在直线上的位置 ($1 \le s_1 < s_2 < \dots < s_m \le 150\,000$)。

输出格式

输出 $n$ 个整数 $c_1, c_2, \dots, c_n$。

子任务

样例

输入格式 1

3 3
1 2 3
1 3 6

输出格式 1

0
4
11

输入格式 2

3 3
3 2 1
1 3 6

输出格式 2

0
5
13

输入格式 3

2 5
2 1
1 3 4 6 7

输出格式 3

0
6

说明

考虑第一个样例。 当 $k=1$ 时，不发生传送。 当 $k=2$ 时，比赛过程如下。图中展示了无人机到达闸门并发生传送的时刻。

1 次传送

+1 次传送，总计 2

+1 次传送，总计 3

无人机 1 完成比赛

+1 次传送，总计 4

无人机 2 完成比赛

当 $k=3$ 时，比赛过程如下。图中展示了无人机到达闸门并发生传送的时刻。

2 次传送

+2 次传送，总计 4

+2 次传送，总计 6

无人机 1 完成比赛 +2 次传送，总计 8

+1 次传送，总计 9

+1 次传送，总计 10

无人机 2 完成比赛 +1 次传送，总计 11

无人机 3 完成比赛