来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 13 套，第 3 题。原题标号：C；原本地编号：Z4P1-13-C。

C. 比较

我们比较两个数的大小，一般是比较数值的大小，即 $9<10$。

但这种比较未免太过简单，是最基本的。

为了使问题更难些，我们把 $1\sim n$ 这 $n$ 个数按字典序大小从小到大排列，此时 $9>10$。

$q$ 次询问第 $k$ 小的数为多少。

输入格式

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

接下来 $q$ 行，每行一个整数 $k$。

输出格式

对于每组询问，输出一行一个数，表示答案。

样例

输入样例 1

10 3
1
2
3

输出样例 1

1
10
2

样例 1 说明

排列后的数列为：$1,10,2,3,4,5,6,7,8,9$。

数据规模与约定

• 数据点 $1$：$n\le9$。
• 数据点 $2\sim3$：$n\le 100$。
• 数据点 $4\sim6$：$n\le 2\times10^3$。
• 数据点 $7\sim10$：无特殊限制。

对于 $100\%$ 的数据，有 $1\le k\le n\le 10^6$，$q=100$。