CF1725D.Deducing Sortability

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 \lt A_2 \lt A_3 \lt A_4 \lt \ldots \lt 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 \lt C_i$ and for each $j \lt i$, $B_j = C_j$.

假设帕克·查内克有一个由 $N$ 个正整数组成的数组 $A$。帕克·查内克将执行若干次操作。在每次操作中，他将执行以下步骤：

1. 选择一个下标 $p$（$1 \leq p \leq N$）；
2. 设 $c$ 为在此操作之前已在下标 $p$ 上执行的操作次数；
3. 将 $A_p$ 的值减少 $2^c$；
4. 将 $A_p$ 的值乘以 $2$。

每次操作后，数组 $A$ 的所有元素都必须仍为正整数。

当且仅当帕克·查内克能够执行零次或多次操作，使得 $A_1 \lt A_2 \lt A_3 \lt A_4 \lt \ldots \lt A_N$ 成立时，称数组 $A$ 是可排序的（sortable）。

帕克·查内克需构造一个长度为 $N$ 的可排序数组 $A$，使其元素和 $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$ 达到最小可能值。若存在多个满足条件的数组，则帕克·查内克必须从中选出字典序最小的那个。

帕克·查内克需完成以下任务：

• 输出该数组的元素和 $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$；
• 接下来给出 $Q$ 个询问。对第 $i$ 个询问，给定一个整数 $P_i$，帕克·查内克需输出 $A_{P_i}$ 的值。

请帮助帕克·查内克解决该问题。

注：设大小均为 $N$ 的两个数组 $B$ 和 $C$，若存在某个下标 $i$，使得 $B_i \lt C_i$，且对所有 $j \lt i$ 均有 $B_j = C_j$，则称数组 $B$ 字典序小于数组 $C$。

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 \lt P_2 \lt \ldots \lt P_Q \leq N$) — the index asked in the $i$-th question.

第一行包含两个整数 $N$ 和 $Q$（$1 \leq N \leq 10^9$，$0 \leq Q \leq \min(N, 10^5)$）—— 分别表示数组 $A$ 所需的长度以及问题的数量。

接下来的 $Q$ 行中，第 $i$ 行包含一个整数 $P_i$（$1 \leq P_1 \lt P_2 \lt \ldots \lt P_Q \leq N$）—— 表示第 $i$ 个问题所询问的下标。

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

输出 $Q+1$ 行。第 $1$ 行包含一个整数，表示 $A_1 + A_2 + A_3 + A_4 + \ldots + A_N$。对于每个 $1 \leq i \leq Q$，第 $(i+1)$ 行包含一个整数，表示 $A_{P_i}$。

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

在第一个例子中，得到的数组 $A$ 为 $[1, 2, 3, 3, 4, 4]$。我们可以看到，通过执行以下操作可将该数组排序：

• 选择下标 $5$，则 $A = [1, 2, 3, 3, 6, 4]$。
• 选择下标 $6$，则 $A = [1, 2, 3, 3, 6, 6]$。
• 选择下标 $4$，则 $A = [1, 2, 3, 4, 6, 6]$。
• 选择下标 $6$，则 $A = [1, 2, 3, 4, 6, 8]$。