Problem Description

There are n piles of stones of sizes a1,?a2,?...,?an lying on the table in front of you.

During one move you can take one pile and add it to the other. As you add pile i to pile j, the size of pile j increases by the current size of pile i, and pile i stops existing. The cost of the adding operation equals the size of the added pile.

Your task is to determine the minimum cost at which you can gather all stones in one pile.

To add some challenge, the stone piles built up conspiracy and decided that each pile will let you add to it not more than k times (after that it can only be added to another pile).

Moreover, the piles decided to puzzle you completely and told you q variants (not necessarily distinct) of what k might equal.

Your task is to find the minimum cost for each of q variants.

Input

The first line contains integer n (1?≤?n?≤?105) — the number of stone piles. The second line contains n space-separated integers: a1,?a2,?...,?an (1?≤?ai?≤?109) — the initial sizes of the stone piles.

The third line contains integer q (1?≤?q?≤?105) — the number of queries. The last line contains q space-separated integers k1,?k2,?...,?kq (1?≤?ki?≤?105) — the values of number k for distinct queries. Note that numbers ki can repeat.

Output

Print q whitespace-separated integers — the answers to the queries in the order, in which the queries are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5
2 3 4 1 1
2
2 3

Output

9 8

Note

In the first sample one way to get the optimal answer goes like this: we add in turns the 4-th and the 5-th piles to the 2-nd one; then we add the 1-st pile to the 3-rd one; we add the 2-nd pile to the 3-rd one. The first two operations cost 1 each; the third one costs 2, the fourth one costs 5 (the size of the 2-nd pile after the first two operations is not 3, it already is 5).

In the second sample you can add the 2-nd pile to the 3-rd one (the operations costs 3); then the 1-st one to the 3-th one (the cost is 2); then the 5-th one to the 4-th one (the costs is 1); and at last, the 4-th one to the 3-rd one (the cost is 2).

題意：給出 n 堆石頭，每次可以將一堆石頭放到另一堆里，代價是移動該堆的大小，現在有 q 次詢問，每次詢問給出一個值 k，代表每堆石頭最多只能移動 k 次，問每次詢問的最小代價

思路：

對于每組樣例，首先對石堆進行排序，由于每堆對多被放 k 次，那么可將每堆石頭視為一個結點，其度為 k，從而從頭到尾構建一個 k 叉樹，其代價為每一個結點的值*路徑長度，并將代價越大的結點盡量放在最高層，這樣就是一個 k 叉的霍夫曼樹

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 500000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;LL a[N]; LL res[N],sum[N]; LL bucket[N]; int main() {LL n;scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+n+1);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];int q;scanf("%d",&q);bool flag=true;int cnt=0;for(int i=1;i<=q;i++){if(n==1)flag=false;else{int k;scanf("%d",&k);if(k>n)k=n;cnt++;if(bucket[k]!=0)res[cnt]=bucket[k];else{LL left=0,right=n-1;LL index=0,tot=1;LL temp=1;while(true){temp*=k;index+=temp;left=max(n-index,(LL)1);res[cnt]+=(sum[right]-sum[left-1])*tot;right=left-1;if(left==1)break;tot++;}bucket[k]=res[cnt];}}}if(flag){for(int i=1; i<=q; i++){printf("%lld ",res[i]);}}else{for(int i=1; i<=q; i++){printf("0 ");}}printf("\n");return 0; }

?

總結

以上是生活随笔為你收集整理的Naughty Stone Piles（CF-226B）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。