Bajtazar 经营着一家烤三明治店。每天有 $n$ 位顾客光顾，第 $i$ 位顾客在时刻 $t_i$ 到达（Bajtazar 可以从时刻 0 开始烘烤）。每位顾客到达后，都会等待 Bajtazar 提供一份刚从烤箱中取出的新鲜三明治。烤箱一次只能烤一个三明治，烘烤过程耗时固定，且烘烤期间不能打开烤箱。

Bajtazar 的烤箱已经很旧了，是时候考虑买个新的了。商店里有多种烤箱可供选择；对 Bajtazar 来说，烤箱的关键参数是烘烤一个三明治所需的时间。当然，Bajtazar 希望烤箱烘烤速度越快越好，但烤箱越快价格越贵，Bajtazar 不确定自己是否负担得起。

Bajtazar 希望顾客等待三明治的总时间尽可能短（他可以在顾客到达之前就开始烘烤，但必须保证烘烤完成的时间不早于顾客到达的时间——毕竟没人喜欢吃冷掉的三明治）。因此，他决定计算不同烤箱下的总等待时间，以便决定购买哪一个。

商店提供 $m$ 种烤箱，第 $i$ 种烤箱烘烤一个三明治的时间为 $d_i$。请帮助 Bajtazar 计算，如果他购买了第 $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