18998번 - Pastry shop 다국어

You are the owner of a pastry shop baking the most delicious pies in town. Everyday, you sell them to $n$ customers -- the $i$-th of them comes at time $t_i$ (but you can begin baking a pie at time 0). Every client, after coming to your shop waits until you serve him his favourite pie straight out of the oven. Nobody likes cold pies, so a customer may wait for a pie, but a pie should not wait for a customer. 

Your oven can bake only one pie at once and cannot be opened during the process. It always takes the same time to bake a pie. Owing to the fact that you know in advance the exact arrival time of each customer, you have optimized your baking schedule in such a way, that the total waiting time of customers is minimal.

However, your current oven is quite worn out and and it's high time to think about buying a new one. You have already done some research and have selected $m$ models which are of interest to you. The most important parameter of each oven is the duration of baking a single pie -- for the $i$-th model this duration equals $d_i$. Of course you would like to have the most time-efficient oven, but you are not sure whether your wallet allows for such a luxury.

To make a rational decision, you would like to gather some useful statistics. For each model, compute the total amount of time your customers would wait, if you decided to purchase that oven and scheduled your baking optimally.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 200\,000$) which are the number of customers and oven models, respectively. 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}$); $t_i$ stands for the moment of arrival of the $i$-th client. Please note that two customers can come to your shop at the same time. In the third line there are $m$ integers $d_1, d_2, \ldots, d_m$ ($1 \leq d_i \leq 10^6$); $d_i$ stands for the duration of baking a single pie in the $i$-th oven model.

You should output exactly $m$ lines; the $i$-th of them should contain exactly one integer -- the minimum total time your customers would wait with optimal baking schedule, assuming you decided to purchase the $i$-th oven model.