Given $n$ numbers $a_1, \dots, a_n$.

A $d$-coding tree is defined as a full binary tree $T$ with exactly $n$ leaves, where the depth of every leaf does not exceed $d$. Each leaf has a weight, and the $n$ weights correspond one-to-one with the elements of $a$.

The total weight of a $d$-coding tree is defined as $\sum\limits_{u\in\text{leaf}} dep_u\cdot w_u$, where $\text{leaf}$ is the set of all leaf nodes, $dep_u$ is the depth of $u$ (the depth of the root is $0$), and $w_u$ is the weight of $u$.

A $d$-Huffman tree is defined as a $d$-coding tree with the minimum total weight.

Given $m$ queries, each providing a $d$, find the total weight of the $d$-Huffman tree. It is guaranteed that $2^d \ge n$, ensuring that a $d$-Huffman tree exists.

Input

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1, \dots, a_n$.

The next $m$ lines each contain an integer $d$, representing a query.

Output

Output $m$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

6 4
1 2 4 7 10 15
3
4
5
6

Output 1

92
88
87
87

Constraints

For $100\%$ of the data, $1 \le n, m \le 2^{18}$, $1 \le a_i \le 10^9$, $1 \le d \le n$, and $2^d \ge n$.

Subtask 1 ($10\%$): $n \le 2^4$.

Subtask 2 ($15\%$): $n \le 2^7$.

Subtask 3 ($20\%$): $n \le 2^{10}$.

Subtask 4 ($25\%$): $m = 1$.

Subtask 5 ($30\%$): No special restrictions.