Fresh Shaobing Waiting Time Minimization

There are \(n\) customers buying freshly baked shaobing. The \(i\)-th customer arrives at time \(t_i\). A customer will only accept a shaobing that is baked no earlier than his arrival time, i.e. the shaobing must be finished baking at time \(\ge t_i\).

There are \(m\) types of ovens. The \(i\)-th oven takes \(d_i\) time units to bake a shaobing. In other words, if an oven starts baking at time \(a\), the shaobing will be ready at time \(a+d_i\).

For each type of oven, if we use a single oven of that type starting at time \(0\), determine the minimum total waiting time of all customers under an optimal baking schedule. The waiting time for a customer is defined as the difference between the time the shaobing is ready and the customer's arrival time.

Note: It is allowed to delay the start of baking such that a shaobing is finished exactly at or after a customer's arrival time.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(m\) denoting the number of customers and the number of oven types, respectively.
2. The second line contains \(n\) space-separated integers \(t_1, t_2, \dots, t_n\) representing the arrival times of the customers.
3. The third line contains \(m\) space-separated integers \(d_1, d_2, \dots, d_m\) where \(d_i\) is the time taken by the \(i\)-th oven type to bake a shaobing.

outputFormat

Output a single line containing \(m\) space-separated integers. The \(i\)-th integer should be the minimum total waiting time achievable using a single oven of the \(i\)-th type starting at time \(0\).

sample

3 2
1 5 6
2 5

7 21