Possible Champions in a Knockout Tournament

In this problem, there is a knockout tournament held in a "ladder-match" style with \(2^k\) contestants. The tournament is organized in \(k\) rounds as follows:

• In the first round, contestants \(1\) and \(2\) face off, contestants \(3\) and \(4\) face off, and so on until contestants \(2^k-1\) and \(2^k\) compete.
• In each subsequent round, only the winners of the previous round remain, and adjacent contestants face off.
• The final round (round \(k\)) is played between the two semifinal winners.

Every contestant \(i\) has an ability value \(a_i\) (an integer in \([0,2^{31}-1]\)). Before each match in round \(R\), a coin toss (i.e. drawing a 0 or 1 uniformly) determines who will be the "host". If the toss results in 0, then the contestant with the smaller index becomes the host; if it is 1, then the one with the larger index is the host. The twist is that the outcome of the match depends only on the host. Specifically, the host wins if and only if his ability is at least \(R\) (i.e. \(a \ge R\)); otherwise, he loses. (Note that the other contestant's ability does not matter.)

Initially, \(n\) contestants have registered (in order) with fixed ability values \(a_1, a_2, \dots, a_n\), and they are assigned indices \(1, 2, \dots, n\) respectively. In order to hold a complete tournament, additional contestants are added such that the total number of contestants becomes \(2^k\) where \(k\) is the smallest nonnegative integer satisfying \(2^k \ge n\). The abilities of these supplemental contestants can be arbitrarily chosen from \([0,2^{31}-1]\).

We say that a contestant (whether originally registered or supplemental) possibly becomes the champion if there exists a way to choose the coin toss outcomes in every match and (if it is a supplemental contestant) an appropriate ability so that they can win every match they play. Note that in order to win a match, a contestant must be designated as the host, and thus in every round they must be the host. Hence, for a contestant to possibly win in round \(R\), they must have ability at least \(R\). In a full tournament of \(k\) rounds, a contestant can be champion if and only if:

• If the contestant is registered (with fixed ability), then \(a_i \ge k\);
• If the contestant is a supplemental contestant, we can choose his ability arbitrarily, so he can always be set to a value \(\ge k\).

Your task is to answer \(m\) queries. For each query with parameter \(c\), consider only the first \(c\) registered contestants. Let \(k\) be the smallest nonnegative integer such that \(2^k \ge c\). We then add \(2^k - c\) supplemental contestants. The answer to the query is the sum of the indices of all contestants (from \(1\) to \(2^k\)) who possibly could become champion in a complete tournament.

Input and output format details are given below.

inputFormat

The input begins with two integers \(n\) and \(m\) \((1 \le n \le 10^5,\; 1 \le m \le 10^5)\) representing the number of registered contestants and the number of queries respectively.

The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 2^{31}-1)\) representing the ability values of the registered contestants in order.

The following line contains \(m\) integers \(c_1, c_2, \dots, c_m\) \((1 \le c_i \le n)\), where each \(c_i\) refers to considering only the first \(c_i\) registered contestants.

outputFormat

For each query, output a single integer — the sum of the indices (of the contestants from \(1\) to \(2^k\)) who can possibly become the champion in the tournament. Print the answers in the order of the queries; each answer should be printed on a separate line.

Note: For registered contestants (indices \(1\) to \(c\)), a contestant can be champion only if his ability \(a_i \ge k\). Supplemental contestants (indices \(c+1\) to \(2^k\)) can always be chosen to have an ability \(\ge k\), so they always count.

sample

3 2
1 2 3
3 1

9
1

</p>