EOJ Monthly 2019.2 (based on February Selection)

B. 解题

单点时限: 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$ 位。保证一定有解。

样例

Input
1249
4
7
3
2
83
Output
3 4
4 4
3 3
2 4

提示

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