在因诺波利斯（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$。
子任务
| 子任务 | 分值 | $n$ | $m$ | $t_i, s_i$ | 附加限制 | 依赖子任务 |
|---|---|---|---|---|---|---|
| 1 | 5 | $n = 2$ | $m \le 50$ | $t_i, s_i \le 100\,000$ | ||
| 2 | 7 | $n \le 50$ | $m \le 50$ | $t_i, s_i \le 100\,000$ | 1 | |
| 3 | 13 | $n \le 1000$ | $m \le 5$ | $t_i, s_i \le 100\,000$ | ||
| 4 | 9 | $n \le 100\,000$ | $m \le 100\,000$ | $t_i, s_i \le 100\,000$ | $s_{i+1} - s_i = s_1$ 对所有 $1 \le i < m$ | |
| 5 | 8 | $n \le 100\,000$ | $m \le 100\,000$ | $t_i, s_i \le 100\,000$ | 所有 $t_i$ 相等 | |
| 6 | 10 | $n \le 100$ | $m \le 100\,000$ | $t_i, s_i \le 100\,000$ | 1, 2 | |
| 7 | 5 | $n \le 100\,000$ | $m \le 100\,000$ | $t_i \le 2, s_i \le 100\,000$ | ||
| 8 | 7 | $n \le 100\,000$ | $m = 2$ | $t_i, s_i \le 100\,000$ | ||
| 9 | 6 | $n \le 10\,000$ | $m \le 100\,000$ | $t_i, s_i \le 100\,000$ | 1, 3, 6 | |
| 10 | 6 | $n \le 50\,000$ | $m \le 100\,000$ | $t_i, s_i \le 100\,000$ | 1, 3, 6, 9 | |
| 11 | 8 | $n \le 100\,000$ | $m \le 100\,000$ | $t_i, s_i \le 100\,000$ | 1, 10 | |
| 12 | 8 | $n \le 100\,000$ | 1, 11 | |||
| 13 | 8 | 无附加限制 | 1, 12 |
样例
输入格式 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 完成比赛