1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int M=1000000,N=200000;
long long x[N+10],pre[N+10],ans[M+10];
int father[N+10],l[N+10];
int n,m;
struct atom{
	long long t;
	int where;
};
int operator < (const atom& k1,const atom& k2){
	return k1.t>k2.t;
}
priority_queue<atom>Q;
int findfather(int k1){
	if (father[k1]==k1) return k1; return father[k1]=findfather(father[k1]);
}
long long K,B;
void add(int R,int w){
	int L=l[R];
	long long k1=1ll*(R-L+1)*(R-L)/2;
	long long k2=x[L]*(R-L+1)+pre[R]-pre[L-1];
	K=K+k1*w; B=B+k2*w;
}
void merge(int k1,int k2){
	//cout<<"merge "<<k1<<" "<<k2<<endl;
	add(k1,-1); add(k2,-1);
	father[k1]=k2; l[k2]=l[k1];
	add(k2,1);
}
int main(){
	scanf("%d%d",&n,&m); 
	for (int i=1;i<=n;i++) scanf("%lld",&x[i+1]); x[1]=0; n++;
	sort(x+1,x+n+1);
	for (int i=1;i<=n;i++) father[i]=i,pre[i]=pre[i-1]+x[i],l[i]=i;
	Q.push((atom){M+10,0});
	for (int i=1;i<n;i++) Q.push((atom){x[i+1]-x[i],i});
	K=0; B=0;
	for (int d=1;d<=M;d++){
		while (Q.top().t<=d){
			atom now=Q.top(); Q.pop();
			int where=now.where;
			if (father[where]!=where) continue;
			merge(where,findfather(where+1));
			where=findfather(where);
			if (where==n) continue;
			long long L=x[l[where]],R=x[where+1];
			long long num=0;
			if (L!=R) num=(R-L-1)/(where-l[where]+1)+1;
			Q.push((atom){num,where});
		}
		ans[d]=d*K+B;
	}
	for (;m;m--){
		int k1; scanf("%d",&k1);
		printf("%lld\n",ans[k1]);
	}
	return 0;
}