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$.

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}$.