Description

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

Input Format

第一行包含两个整数 $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$）。

Output Format

输出 $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

Hint

样例 $1$ 解释：

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

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

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

各子任务特殊性质表格：