CF226B.Naughty Stone Piles

There are n piles of stones of sizes _a_1, _a_2, ..., a__n 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.

桌面上有 $n$ 堆石子，大小分别为 $a_1,\,a_2,\,\dots,\,a_n$。

在一次操作中，你可以选择一堆石子，并将其合并到另一堆中。当把第 $i$ 堆合并到第 $j$ 堆时，第 $j$ 堆的大小增加为当前第 $i$ 堆的大小，而第 $i$ 堆则消失。该合并操作的代价等于被合并堆（即第 $i$ 堆）的当前大小。

你的任务是求出将所有石子合并为一堆所需的最小总代价。

为了增加挑战性，这些石子堆秘密结成同盟，规定：每一堆石子最多只能作为被合并目标（即接收方）被合并 $k$ 次（超过 $k$ 次后，该堆只能被合并到其他堆中，而不能再接收合并）。

此外，石子堆们决心彻底迷惑你，向你提供了 $q$ 个可能的 $k$ 值（这些值不一定互不相同）。

你的任务是：对这 $q$ 个 $k$ 值中的每一个，分别求出对应的最小总代价。

The first line contains integer n (1 ≤ n ≤ 105) — the number of stone piles. The second line contains n space-separated integers: _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 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 _k_1, _k_2, ..., k__q (1 ≤ k__i ≤ 105) — the values of number k for distinct queries. Note that numbers k__i can repeat.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——石堆的数量。
第二行包含 $n$ 个用空格分隔的整数：$a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^9$）——各石堆的初始大小。

第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）——查询次数。
最后一行包含 $q$ 个用空格分隔的整数 $k_1,\,k_2,\,\dots,\,k_q$（$1 \leq k_i \leq 10^5$）——各次查询中参数 $k$ 的取值。注意：$k_i$ 的值可以重复。

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.

输出 q 个用空格分隔的整数——即按输入中查询给出的顺序，依次输出各查询的答案。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

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).

在第一个样例中，一种得到最优答案的方法如下：我们依次将第 4 堆和第 5 堆合并到第 2 堆；然后将第 1 堆合并到第 3 堆；最后将第 2 堆合并到第 3 堆。前两次操作的代价各为 1；第三次操作代价为 2；第四次操作代价为 5（注意：第 2 堆在前两次操作后的大小并非 3，而已经是 5）。

在第二个样例中，你可以先将第 2 堆合并到第 3 堆（操作代价为 3）；然后将第 1 堆合并到第 3 堆（代价为 2）；接着将第 5 堆合并到第 4 堆（代价为 1）；最后将第 4 堆合并到第 3 堆（代价为 2）。