Pastry shop

You are the owner of a pastry shop that bakes the best pies in town. Every day, $n$ customers come to your shop, and the $i$-th customer arrives at time $t_i$. You can start baking a pie at time 0. After arriving, a customer waits until you serve the favourite pie straight out of the oven. Nobody likes cold pies, so a customer may wait for a pie, but a pie must not wait for a customer.

Your oven can bake only one pie at a time and cannot be opened during baking. Every pie takes the same time to bake. You know the arrival time of each customer in advance, so you schedule the baking to minimize the total waiting time of the customers.

Your current oven is worn out, so you are thinking about buying a new one. You have chosen $m$ oven models. The duration of baking one pie in the $i$-th model is $d_i$. You want the fastest oven, but you are not sure whether you can afford it. For each model, compute the total time the customers would wait if you bought that oven and scheduled the baking optimally.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 200000$). The second line contains $n$ integers $t_1, t_2, \ldots, t_n$ ($0 \leq t_1 \leq t_2 \leq \ldots \leq t_n \leq 10^{12}$). Two customers can arrive at the same time. The third line contains $m$ integers $d_1, d_2, \ldots, d_m$ ($1 \leq d_i \leq 10^6$).

Print exactly $m$ lines. The $i$-th line contains one integer, the minimum total waiting time of the customers when the $i$-th oven model is used with optimal baking.