Deducing Sortability
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:
- 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$.
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.
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}$.
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}$.
6 3
1
4
5
1 0
17
1
3
4
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]$.