Let's say Pak Chanek has an array $A$ consisting of $N$ positive integers. Pak Chanek will do a number of operations. In each operation, Pak Chanek will do the following:

Choose an index $p$ ($1 \leq p \leq N$).

Let $c$ be the number of operations that have been done on index $p$ before this operation.

Decrease the value of $A_p$ by $2^c$.

Multiply the value of $A_p$ by $2$.

After each operation, all elements of $A$ must be positive integers.

An array $A$ is said to be sortable if and only if Pak Chanek can do zero or more operations so that $A_1 < A_2 < A_3 < A_4 < \ldots < A_N$.

Pak Chanek must find an array $A$ that is sortable with length $N$ such that $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$ is the minimum possible. If there are more than one possibilities, Pak Chanek must choose the array that is lexicographically minimum among them.

Pak Chanek must solve the following things:

Pak Chanek must print the value of $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$ for that array.

$Q$ questions will be given. For the $i$-th question, an integer $P_i$ is given. Pak Chanek must print the value of $A_{P_i}$.

Help Pak Chanek solve the problem.

Note: an array $B$ of size $N$ is said to be lexicographically smaller than an array $C$ that is also of size $N$ if and only if there exists an index $i$ such that $B_i < C_i$ and for each $j < i$, $B_j = C_j$.


-----Input-----

The first line contains two integers $N$ and $Q$ ($1 \leq N \leq 10^9$, $0 \leq Q \leq \min(N, 10^5)$) — the required length of array $A$ and the number of questions.

The $i$-th of the next $Q$ lines contains a single integer $P_i$ ($1 \leq P_1 < P_2 < \ldots < P_Q \leq N$) — the index asked in the $i$-th question.


-----Output-----

Print $Q+1$ lines. The $1$-st line contains an integer representing $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$. For each $1 \leq i \leq Q$, the $(i+1)$-th line contains an integer representing $A_{P_i}$.


-----Examples-----

Input
6 3
1
4
5
Output
17
1
3
4
Input
1 0
Output
1


-----Note-----

In the first example, the array $A$ obtained is $[1, 2, 3, 3, 4, 4]$. We can see that the array is sortable by doing the following operations:

Choose index $5$, then $A = [1, 2, 3, 3, 6, 4]$.

Choose index $6$, then $A = [1, 2, 3, 3, 6, 6]$.

Choose index $4$, then $A = [1, 2, 3, 4, 6, 6]$.

Choose index $6$, then $A = [1, 2, 3, 4, 6, 8]$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Bit manipulation

Sorting

Mathematics


Solutions:
def ev(x):
	k = 0
	while x % 2 == 0:
		x //= 2
		k += 1
	return x + k
(p, q) = [int(i) for i in input().split()]
(t, s, sum) = (1, 1, 0)
while True:
	ss = s + (t + 1) // 2
	if ss > p:
		m = p - s + 1
		sum += m * t
		break
	sum += t * ((t + 1) // 2)
	s = ss
	t += 1
mx = t - 2 * m + 1
print(sum)
(mul, ded, turn) = (0, 0, 0)
t -= 0 if mx == turn else 1
for i in range(q):
	x = int(input())
	if x == 1:
		print(1)
		continue
	while True:
		if x - ded <= t:
			print(ev(x - ded) + mul)
			break
		ded += (t + 1) // 2
		turn += 1
		mul += 1
		t -= 0 if mx == turn else 1