B. 解题 - EOJ Monthly 2019.2 (based on February Selection)

仪表盘所有提交榜单题解

单点时限: 2.0 sec

内存限制: 1024 MB

“我把房门上锁，并非为了不让她进去，而是为了防止自己逃到她身边”。

她又被数学难住了。QQ 小方当然是不会对女生说”不”的。

她的数学题是这样的，她得到了一个十进制大整数，这个大整数只包含 $1$ - $9$ 这 $9$ 个数字。

现在，要求选出其中连续的一段数字，把其他未被选中的数字全部变成 $0$ ，并且使得变换以后的大整数恰好是 $m$ 的倍数。

QQ 小方为了表现自己的能力，所以一口答应给她写出在所有可能的数里面最小的一个。

但是她的问题太多了，她对于这一个大整数，需要对于 $q$ 个不尽相同的 $m$ 分别给出答案。

但是 QQ 小方自己不会。只能来求助你了，你能帮他解答吗？

第一行包含一个大整数，这个整数的位数为 $n$ ( $1 \leq n \leq 10^{6}$ )。

第二行一个整数 $q$ ( $1 \leq q \leq 500$ ) 代表询问次数。

对于每一个询问，包含一行一个整数，表示第 $i$ 次询问的 $m_{i}$ ( $1 \leq m_{i} \leq 5 \times 10^{7}$ )。

保证 $\sum_{i = 1}^{q} m_{i} \leq 5 \times 10^{7}$ 。

对于每一个询问输出两个整数 $l, r$ 表示保留第 $l$ 到第 $r$ 位。保证一定有解。

Input

Output

对于样例：
$1249$ 这个数中，可选出的最小的 $7$ 的倍数是 $49$ ，最小的 $3$ 的倍数是 $9$ ， $2$ 的倍数是 $40$ ， $83$ 的倍数是 $249$ 。

NaN

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2019.2 (based on February Selection)