题目背景

T. B. D.

题目描述

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

例如，$k=3$ 时，$f(10)=\texttt{101}$。

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

• 定义 $s_0$ 为空字符串；
• 对于 $n\ge1$，定义 $s_n=s_{n-1}\odot f(n)$（本题中 $\odot$ 表示字符串拼接）。

例如，$k=3$ 时，$s_4=\texttt{121011}$。

再令无限长字符串

$$S=s_1\odot s_2\odot s_3\odot\cdots=\bigodot_{i=1}^\infty s_i$$

例如，$k=10$ 时，$S=\texttt{112123123412345}\cdots$。

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

输入格式

从文件 digit.in 中读入。

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

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

输出格式

输出到文件 digit.out 中。

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

输入输出样例

输入样例 1

10 2
3
8

输出样例 1

2
2

样例 1 说明

如题所述，$k=10$ 时，$S=\texttt{11}{\underline{\color{red}\texttt2}}\texttt{1231}{\underline{\color{blue}\texttt2}}\texttt{3412345}\cdots$。标红的为第 $3$ 位，标蓝的为第 $8$ 位。

样例 2

见下发压缩包中 $\textbf{\textit{digit2.in}}$ 与 $\textbf{\textit{digit2.ans}}$。

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

样例 3

见下发压缩包中 $\textbf{\textit{digit3.in}}$ 与 $\textbf{\textit{digit3.ans}}$。

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

样例 4

见下发压缩包中 $\textbf{\textit{digit4.in}}$ 与 $\textbf{\textit{digit4.ans}}$。

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

说明

数据规模与约定

测试点	$k$	$d\le$
$1\sim2$	$=10$	$10^3$
$3\sim5$	$=2$	无特殊限制
$6\sim8$	$=3$
$9\sim10$	无特殊限制

对于 $100\%$ 的数据，有 $2\le k\le 10$，$1\le q\le 100$，$1\le d\le 10^9$。