下发文件

对于一个长度为 $n$ 的正整数数组 $a$，你可以进行如下操作：

• 创建一个长度为 $n$ 的数组 $c$，初始全为 $0$
• 进行任意多次以下操作：选择一个 $1\le x\le n$，先 $a_x:=(a_x-2^{c_{x}})\times 2$，再 $c_x:=c_x+1$

如果你可以用该操作使 $a$ 严格递增且操作后为正整数，则称 $a$ 为一个好的数组。

你希望找到一个长度为 $n$ 的好的数组 $a$ 使得 $\sum_{i=1}^{n} a_i$ 最小。你希望找出在所有的这样的 $\sum_{i=1}^{n} a_i$ 最小的好的数组中，字典序最小的好的数组。

由于 $n$ 非常大，所以你只需要回答 $\sum_{i=1}^{n} a_i$。同时，给定 $Q$ 个 $[1,n]$ 的正整数 $b_1,\dots,b_{Q}$，你需要对于每个 $i$ 输出 $a_{b_{i}}$。

输入格式

第一行两个整数 $n,Q$。

第二行 $Q$ 个正整数 $b_1,b_2,\dots,b_Q$。

输出格式

第一行一个整数表示 $\sum_{i=1}^{n} a_i$。

后面 $Q$ 行共 $Q$ 个正整数表示 $a_{b_1},a_{b_2},\dots,a_{b_Q}$。

样例 1 输入

10 10
1 2 3 4 5 6 7 8 9 10

样例 1 输出

38
1
2
3
3
5
4
4
5
5
6

样例 2

见选手目录下 $halation/ex\_halation2.in$ 与 $halation/ex\_halation2.out$

该样例满足子任务 $2$ 的限制。

样例 3

见选手目录下 $halation/ex\_halation3.in$ 与 $halation/ex\_halation3.out$

该样例满足子任务 $3$ 的限制。

数据范围

对于所有数据，满足 $1\le n\le 10^9$，$1\le Q\le 10^5$。