2685. 「BalticOI 2013」Brunhilda 的生日 Brunhilda’s Birthday

题目描述

给定 $m$ 个素数和 $Q$ 个询问。每个询问有 $n$ 个人，每次操作可以任意选择其中的一个素数 $p$（素数可以重复使用），然后去掉剩余人数 $\bmod p$ 个人。对于每个询问，我们想知道，至少需要多少步操作才能去掉所有人。

输入格式

第一行：素数个数 $m$ 和询问个数 $Q$（$1 \le m \le 100\,000$, $1 \le Q \le 100\,000$）

第二行：$m$ 个素数 $p_i$（$2 \le p_i \le 10\,000\,000$）

下面 $Q$ 行：$n$（$1 \le n \le 10\,000\,000$）

输出格式

$Q$ 行答案。如果无解，输出 oo。

样例

输入

2 2
2 3
5
6

输出

3
oo

解释：

• $n=5$：可以用 $p=3$ 去掉 $5 \bmod 3 = 2$ 人，剩下 3 人；再用 $p=2$ 去掉 $3 \bmod 2 = 1$ 人，剩下 2 人；再用 $p=2$ 去掉 $2 \bmod 2 = 0$ 人，剩下 2 人（这里有问题，应该是去掉后剩下的人数）。实际上正确操作需要 3 步。
• $n=6$：无解，因为 $6$ 不能被任何 $p_i$ 整除，且 $6 \bmod p_i$ 无法达到 0。

数据范围与提示

对于 $20\%$ 的测试数据，$m, n_j, Q \le 10\,000$

对于另外 $20\%$ 的测试数据，$Q = 1$

对于所有数据，$1 \le m \le 100\,000$, $1 \le Q \le 100\,000$, $2 \le p_i \le 10\,000\,000$, $1 \le n_j \le 10\,000\,000$。