题目描述

给定一个整数 $k$，对于任意正整数 $n$，先将 $n$ 转化为 $k$ 进制，再将其转化为字符串，记结果为 $f(n)$。

例如，$k=3$ 时，$f(10)=101$。

接下来，递归地定义字符串 $s_n$ 如下：

• 定义 $s_0$ 为空字符串；
• 对于 $n\ge 1$，定义$$s_n=s_{n-1}\operatorname{\small\frown} f(n)$$ 其中本题中 $\operatorname{\small\frown}$ 表示字符串拼接。

例如，$k=3$ 时：

• $f(1)=1$
• $f(2)=2$
• $f(3)=10$
• $f(4)=11$

因此：

• $s_1=1$
• $s_2=12$
• $s_3=1210$
• $s_4=121011$

再令无限长字符串

$$S=s_1\operatorname{\small\frown}s_2\operatorname{\small\frown}s_3\operatorname{\small\frown}\cdots$$

例如，$k=10$ 时，

$$S=112123123412345\cdots$$

现在有 $q$ 次询问，每次询问字符串 $S$ 的第 $d$ 位上的数字。

输入格式

从文件 digit.in 中读入。

第一行两个整数 $k,q$，表示进制数与询问数量。

接下来 $q$ 行，每行一个整数 $d$，表示询问 $S$ 的第 $d$ 位上的数字。

输出格式

输出到文件 digit.out 中。

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

输入输出样例 #1

10 2
3
8

2
2

样例说明

如题所述，当 $k=10$ 时：

$$S=112123123412345\cdots$$

其中第 $3$ 位是 2，第 $8$ 位也是 2。

输入输出样例 #2

见下发压缩包中的 digit2.in 与 digit2.ans。

该样例符合测试点 $1\sim 2$ 的限制。

输入输出样例 #3

见下发压缩包中的 digit3.in 与 digit3.ans。

该样例符合测试点 $3\sim 5$ 的限制。

输入输出样例 #4

见下发压缩包中的 digit4.in 与 digit4.ans。

该样例符合测试点 $6\sim 8$ 的限制。

说明/提示

数据规模与约定

对于 $100\%$ 的数据，满足：

• $2\le k\le 10$
• $1\le q\le 100$
• $1\le d\le 10^9$

测试点限制如下：

测试点	$k$	$d\le$
$1\sim 2$	$10$	$10^3$
$3\sim 5$	$2$	无特殊限制
$6\sim 8$	$3$
$9\sim 10$	无特殊限制