Bajtazar owns a stall where he sells zapiekanki (toasted sandwiches). Every day, $n$ customers visit the stall, with the $i$-th customer arriving at time $t_i$ (Bajtazar can start baking at time $0$). Each customer, upon arriving at the stall, waits until Bajtazar serves them a fresh zapiekanka, taken out of the oven just a moment ago. The oven can bake only one zapiekanka at a time, it always takes the same amount of time, and the oven cannot be opened while baking.

Bajtazar's oven is quite worn out, and it is high time to think about buying a new one. There is a large selection of good ovens in the store; the key parameter for Bajtazar is the baking time of a zapiekanka. Naturally, Bajtazar would like an oven that bakes as quickly as possible, but the faster the oven, the more expensive it is, and Bajtazar does not know if he can afford it.

Bajtazar wants the total waiting time of the customers to be as short as possible (he can start baking a zapiekanka before the customer arrives, but he must finish baking it no earlier than the moment the customer arrives – after all, no one likes to eat cold zapiekanki). He has decided to calculate this time for various ovens and then decide which one to purchase.

The store offers $m$ ovens, where the $i$-th one bakes a zapiekanka in time $d_i$. Help Bajtazar and calculate, for each of them, what the total waiting time of the customers would be if Bajtazar were to buy it.

Input

The first line of standard input contains two integers $n$ and $m$ ($1 \le n, m \le 200\,000$) representing the number of customers and the number of ovens. The second line contains a sequence of $n$ integers $t_1, t_2, \dots, t_n$ ($0 \le t_1 \le t_2 \le \dots \le t_n \le 10^{12}$); the number $t_i$ denotes the time at which the $i$-th customer arrives at the stall. Note that it may happen that two customers arrive at the stall at exactly the same moment. The third line contains a sequence of $m$ integers $d_1, d_2, \dots, d_m$ ($1 \le d_i \le 10^6$); the number $d_i$ denotes the baking time of a zapiekanka in the $i$-th oven.

Output

Standard output should contain exactly $m$ lines; the $i$-th line should contain a single integer – the minimum total waiting time of the customers using the optimal baking strategy for the $i$-th oven from the input.

Examples

Input 1

4 3
3 10 11 23
4 2 5

Output 1

4
1
6