单点时限: 2.0 sec
内存限制: 1024 MB
“我把房门上锁,并非为了不让她进去,而是为了防止自己逃到她身边”。
她又被数学难住了。QQ 小方当然是不会对女生说”不”的。
她的数学题是这样的,她得到了一个十进制大整数,这个大整数只包含 $1$ - $9$ 这 $9$ 个数字。
现在,要求选出其中连续的一段数字,把其他未被选中的数字全部变成 $0$,并且使得变换以后的大整数恰好是 $m$ 的倍数。
QQ 小方为了表现自己的能力,所以一口答应给她写出在所有可能的数里面最小的一个。
但是她的问题太多了,她对于这一个大整数,需要对于 $q$ 个不尽相同的 $m$ 分别给出答案。
但是 QQ 小方自己不会。只能来求助你了,你能帮他解答吗?
第一行包含一个大整数,这个整数的位数为 $n$ ($1\le n\le 10^6$)。
第二行一个整数 $q$ ($1\le q\le 500$) 代表询问次数。
对于每一个询问,包含一行一个整数,表示第 $i$ 次询问的 $m_i$ ($1\le m_i\le 5 \times 10 ^7$)。
保证 $\sum_{i=1}^{q}m_i\le 5 \times 10^7$ 。
对于每一个询问输出两个整数 $l,r$ 表示保留第 $l$ 到第 $r$ 位。保证一定有解。
1249 4 7 3 2 83
3 4 4 4 3 3 2 4
对于样例:
$1249$ 这个数中,可选出的最小的$7$的倍数是$49$,最小的$3$的倍数是$9$,$2$的倍数是$40$,$83$的倍数是$249$。