Description:
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:
1. Choose an index $$$p$$$ ($$$1 \leq p \leq N$$$).
2. Let $$$c$$$ be the number of operations that have been done on index $$$p$$$ before this operation.
3. Decrease the value of $$$A_p$$$ by $$$2^c$$$.
4. 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 Format:
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 Format:
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}$$$.
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]$$$.