imicola真的不是柚子厨(hard vision)
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

你轻松地解决了imicola的简单问题,但这似乎并不能证明他不是柚子厨

imicola看到你秒杀了他的题目后大为震惊,他认为你只是运气好,或者你也是深藏不露的柚子厨,看穿了他简单的小把戏。为了捍卫自己最后的尊严,他决定给你展示一下什么叫做真正的“无限”!

“循环拼接也太简单了,” imicola说道,“真正的无限,是不断增长的!看好了,这次的序列将会是无穷无尽、永不重复的!”

如果你还能解决这个问题,imicola就将心甘情愿地接受“柚子厨”的称号,并把他的柚子社游戏珍藏送给你一份

注:本题进行悬赏

这次,imicola定义了一个新的无限字符串 S

S 由正整数 n 的所有正整数倍(n,2n,3n,4n,...)的十进制表示按顺序拼接而成。

例如,当 n=3 时,这个序列是 3, 6, 9, 12, 15, ...,拼接成的无限字符串 S3691215...

又例如,当 n=10 时,这个序列是 10, 20, 30, ...,拼接成的无限字符串 S102030...

imicola会给你两个正整数 nq,你需要回答他 q 次询问,每次询问imicola会给你一个数 k,你需要告诉他字符串 S 的第 k 个字符(从1开始计数)是什么。

输入描述:

第一行,输入两个正整数n,q(1 \le n \le 2\times10^{9},q\le2\times10^5)

接着q行,每行输入一个正整数k (1 \le k \le 3 \times 10^{9})表示查询的数

输出描述:

输出q行,每行输出一个数字表示 S 的第 k 个数字
示例1

输入

复制
10 10
3
101
11
9
1
100
99
10
2
999

输出

复制
2
7
6
5
1
3
0
0
0
7

说明

数字10进行上述无限序列变换后变成10203040506070... ,对于第一个询问,我们可以显然发现第3个数位对应的数是2