题目描述

星际观测站正在校准一组星轨编号。给定一个长度为 $n$ 的正整数序列 $a$，每个位置都有一个独立的校准计数器。

校准开始前，创建一个长度为 $n$ 的数组 $c$，初始时所有 $c_i=0$。

之后你可以进行任意多次如下校准操作：

• 选择一个位置 $1\le x\le n$；
• 先令

• 再令

如果经过若干次校准后，序列 $a$ 可以变成一个严格递增的正整数序列，那么称原序列 $a$ 为一个 可校准序列。

现在你希望构造一个长度为 $n$ 的可校准序列 $a$，并满足：

1. $\sum_{i=1}^{n}a_i$ 尽可能小；
2. 在所有总和最小的方案中，序列 $a$ 的字典序尽可能小。

由于 $n$ 可能非常大，你不需要输出整个序列。你只需要输出最小的总和，并回答若干个指定位置上的值。

给定 $Q$ 个位置 $b_1,b_2,\dots,b_Q$，请输出最优序列中这些位置对应的 $a_{b_i}$。

输入格式

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

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

输出格式

第一行输出一个整数，表示最小可能的

接下来 $Q$ 行，第 $i$ 行输出最优序列中的 $a_{b_i}$。

样例 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$。