题目描述

有一个整数 $n$ 以及一个长度为 $m$ 的素数表 $p$。

您可以进行任意多次操作，每一次操作时，您选择一个素数 $p_i$，这会使得 $n\to \lfloor \frac{n}{p_i}\rfloor\times p_i$。

您的目标是求出使得 $n$ 变为 $0$ 的最小操作数，如果不可能变为 $0$，请输出 oo。

为了增加难度，您需要回答 $Q$ 组 $n$。

输入格式

第一行为两个整数 $m,Q$。

接下来一行 $m$ 个整数 $p$。

接下来 $Q$ 行，一行一个整数 $n$，表示每一次询问给出的 $n$。

输出格式

对于每一个询问，求出使得 $n$ 变为 $0$ 的最小操作数，如果不可能变为 $0$，请输出 oo。

2 2
2 3
5
6

3
oo

提示

数据范围及限制

• 对于 $20$ 分的数据，保证 $m,n,Q\le 10^4$。
• 对于另外 $20$ 分的数据，保证 $Q=1$。
• 对于 $100\%$ 的数据，保证 $1\le m,Q\le 10^5$，$2\le p_i\le 10^7$ 且 $p_i$ 为素数，$1\le n\le 10^7$。

说明

本题译自 Baltic Olympiad in Informatics 2013 Day 2 T1 Brunhilda’s Birthday。

因为译题人找不到合适的设置，所以本题满分 $110$ 分。