Problem Description

There is an integer $n$ and a prime list $p$ of length $m$.

You may perform any number of operations. In each operation, you choose a prime $p_i$, which changes $n$ to $n \to \lfloor \frac{n}{p_i} \rfloor \times p_i$.

Your goal is to find the minimum number of operations needed to make $n$ become $0$. If it is impossible to make it $0$, output oo.

To make it harder, you need to answer $Q$ queries of $n$.

Input Format

The first line contains two integers $m, Q$.

The next line contains $m$ integers $p$.

The next $Q$ lines each contain one integer $n$, representing the value of $n$ given in each query.

Output Format

For each query, output the minimum number of operations needed to make $n$ become $0$. If it is impossible, output oo.

2 2
2 3
5
6

3
oo

Hint

Constraints and Limits

• For the testdata worth $20$ points, it is guaranteed that $m, n, Q \le 10^4$.
• For another $20$ points of testdata, it is guaranteed that $Q = 1$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le m, Q \le 10^5$, $2 \le p_i \le 10^7$ and $p_i$ is prime, and $1 \le n \le 10^7$.

Notes

This problem is translated from Baltic Olympiad in Informatics 2013 Day 2 T1 Brunhilda’s Birthday.

Because the translator could not find a suitable setting, this problem has a full score of $110$ points.

Translated by ChatGPT 5