题意：给定一个序列，多次询问
将a数组从小到大排序，下面那个值只有不超过32种，于是预处理f[i][j]，表示分母为i时，aj/i的前缀和是多少。
然后对于一个给定的p，一定将分母划分成了一些连续的段落，通过枚举这些分母，二分获得分母变化的位置，将区间和累计进答案。
注意，对于给定的p，一个分母控制的某段区间是a的元素属于p^i+1到p^(i+1)的这段。
复杂度log^2n。
#include<cstdio>
//#include<cmath>
#include<algorithm>
using namespace std;
int f,cc;
void R(int &x){
cc=0;f=1;
for(;cc<'0'||cc>'9';cc=getchar())if(cc=='-')f=-1;
for(x=0;cc>='0'&&cc<='9';cc=getchar())(x*=10)+=(cc-'0');
x*=f;
}
#define MOD 1000000000
typedef long long ll;
int T,n,m,a[35][500005];
ll c[500005];
//int poses[100005][35];
//double Log(const int &p,const int &x){
// return log((double)x)/log((double)p);
//}
int main(){
R(T);
for(;T;--T){
R(n); R(m);
for(int i=1;i<=n;++i){
R(a[1][i]);
}
sort(a[1]+1,a[1]+n+1);
for(int i=1;i<=n;++i){
c[i]=(ll)a[1][i];
}
for(int i=1;i<=n;++i){
for(int j=2;j<=32;++j){
a[j][i]=a[1][i]/j;
}
}
for(int i=1;i<=32;++i){
for(int j=1;j<=n;++j){
a[i][j]=(a[i][j]+a[i][j-1])%MOD;
}
}
// for(int p=2;p*p<=MOD;++p){
// for(int i=1;i<=32;++i){
// if((int)(ceil(Log(p,c[n]))+0.5)<i){
// poses[p][i]=n+1;
// continue;
// }
// int l=1,r=n;
// while(l<r){
// int mid=(l+r>>1);
// if((int)(ceil(Log(p,c[mid]))+0.5)>=i){
// r=mid;
// }
// else{
// l=mid+1;
// }
// }
// poses[p][i]=l;
// }
// }
int p;
ll ans=0;
int popo[35];
for(int zu=1;zu<=m;++zu){
R(p);
// if((ll)p*(ll)p<=(ll)MOD){
// for(int i=1;i<32;++i){
// if(poses[p][i]>n){
// break;
// }
// ans=(ans+((ll)zu*(ll)((a[i][poses[p][i+1]-1]-a[i][poses[p][i]-1]+MOD)%MOD))%(ll)MOD)%(ll)MOD;
// }
// }
// else{
ll pp=1;
for(int i=1;i<32;++i){
ll* be=upper_bound(c+1,c+n+1,pp);
if(be-c>n){
break;
}
pp*=(ll)p;
ans=(ans+((ll)zu*(ll)((a[i][upper_bound(c+1,c+n+1,pp)-c-1]-a[i][be-c-1]+MOD)%MOD))%(ll)MOD)%(ll)MOD;
}
// }
}
printf("%lld\n",ans);
}
return 0;
}