브룬힐데의 생일

시간 제한1초메모리 제한256 MB

요약

주어진 소수 집합의 수를 불러 n을 p*floor(n/p)로 바꾸는 과정을 거쳐 0으로 만드는 최소 호출 횟수를 각 n에 대해 구하고, 불가능하면 oo를 출력한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 정수론, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

브룬힐데는 곧 있을 생일 파티를 위해 다음과 같은 놀이를 준비했다. 파티에 온 아이들은 어떤 수 $k$ 가 외쳐질 때까지 이리저리 뛰어논다. $k$ 가 외쳐지면 아이들은 정확히 $k$ 명씩 무리를 짓는다. $k$ 명이 남아 있는 동안 계속 $k$ 명짜리 무리를 만들고, 마지막에 $k$ 명을 채우지 못하고 남은( $k$ 명 미만인) 아이들은 놀이에서 빠진다(탈락한다). 완전한 무리를 이룬 아이들은 놀이에 남는다. 이렇게 여러 번 수를 외치며 놀이를 이어 가고, 남은 아이가 한 명도 없으면 놀이가 끝난다.

바꿔 말하면, 현재 아이가 $n$ 명일 때 수 $k$ 를 외치면 $\lfloor n/k \rfloor$ 개의 무리가 만들어져 $k \cdot \lfloor n/k \rfloor$ 명이 남고, 나머지 $n \bmod k$ 명은 탈락한다.

수를 외치는 역할은 브룬힐데의 아버지 보탄이 맡는다. 보탄은 아무 수나 외칠 수 없고, 주어진 서로 다른 소수 $m$ 개의 목록에서만 골라야 하며, 같은 소수를 여러 번 외쳐도 된다. 보탄은 놀이를 가능한 한 적은 횟수로 끝내고 싶다.

파티에 올 아이의 수는 아직 정해지지 않았다. 서로 다른 아이 수 $n_1, \dots, n_Q$ 각각에 대해, 보탄이 놀이를 끝내기 위해 외쳐야 하는 최소 횟수를 구하라. 어떻게 해도 놀이를 끝낼 수 없다면, 무한대를 뜻하는 문자열 oo(소문자 o 두 개)를 대신 출력한다.

입력

첫째 줄에 정수 $m$ 과 $Q$ 가 주어진다.

둘째 줄에 보탄이 외칠 수 있는 서로 다른 소수 $p_i$ ( $1 \le i \le m$ )가 오름차순으로 $m$ 개 주어진다.

이어지는 $Q$ 개의 줄에는 각각 아이 수를 나타내는 정수 $n_j$ ( $1 \le j \le Q$ )가 하나씩 주어진다.

출력

$Q$ 개의 줄을 출력한다. $j$ 번째 줄에는 $n_j$ 에 대한 답을 출력한다. 보탄이 놀이를 끝낼 수 있으면 필요한 최소 외침 횟수(정수)를, 끝낼 수 없으면 문자열 oo를 출력한다.

제한

$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$
$p_i$ 는 서로 다른 소수이며 오름차순으로 주어진다.

예제2

예제 1
입력
```
2 2
2 3
5
6
```
예상 출력
```
3
oo
```
예제 2
입력
```
2 7
2 3
1
2
3
4
5
6
7
```
예상 출력
```
1
1
2
3
3
oo
oo
```