你是这家镇上最美味的糕点店的老板。每天，你都要向 $n$ 位顾客出售糕点——第 $i$ 位顾客在时间 $t_i$ 到达（但你可以在时间 0 开始烘焙）。每位顾客在到达店里后，会一直等待直到你为他端出刚出炉的糕点。没有人喜欢冷掉的糕点，所以顾客可以等待糕点，但糕点不能等待顾客。

你的烤箱一次只能烘焙一个糕点，且在烘焙过程中不能打开。烘焙一个糕点所需的时间总是固定的。由于你预先知道每位顾客的准确到达时间，你已经优化了烘焙计划，使得顾客的总等待时间最小化。

然而，你目前的烤箱已经相当破旧，是时候考虑买一个新的了。你已经做了一些研究，并选出了 $m$ 款你感兴趣的型号。每款烤箱最重要的参数是烘焙单个糕点所需的时间——对于第 $i$ 款型号，这个时间等于 $d_i$。当然，你希望拥有最高效的烤箱，但你不确定你的钱包是否允许这种奢侈。

为了做出理性的决定，你想要收集一些有用的统计数据。对于每一款型号，请计算如果你决定购买该烤箱并优化烘焙计划，顾客的总等待时间是多少。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 200\,000$)，分别表示顾客数量和烤箱型号数量。第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$ ($0 \le t_1 \le t_2 \le \dots \le t_n \le 10^{12}$)，其中 $t_i$ 表示第 $i$ 位顾客的到达时间。请注意，两位顾客可能在同一时间到达。第三行包含 $m$ 个整数 $d_1, d_2, \dots, d_m$ ($1 \le d_i \le 10^6$)，其中 $d_i$ 表示第 $i$ 款烤箱型号烘焙单个糕点所需的时间。

输出格式

你需要输出恰好 $m$ 行；第 $i$ 行应包含一个整数，表示如果你决定购买第 $i$ 款烤箱型号，在最优烘焙计划下顾客的总等待时间。

样例

输入 1

4 3
3 10 11 23
4 2 5

输出 1

4
1
6