Baltic Olympiad in Informatics: 2013 Day 2, Problem 1

Except for her affinity towards old armours, Brunhilda is a normal seven year old girl. Thus, she is planning the perfect birthday party, for which she has invented the following game: All children run around until some number ~k~ is announced. Then all children try to form groups of exactly ~k~ people. As long as at least ~k~ children are left over, further groups of ~k~ children are formed. In the end, less than ~k~ children are left over and will be eliminated (not literally of course) from the game. The game continues with further numbers announced, and ends if all children are out.

Brunhilda asked her father Wotan to announce the numbers in the game. Wotan does not like this game and announced ~\infty~ when they first tried it. Brunhilda thinks this would be quite embarrassing at the party, and so she gave him a list of ~m~ prime numbers from which he can choose for each call; he may use the same number more than once.

Wotan would like to end the game as soon as possible since he has tickets for a match of his favourite football club FC Asgard. Unfortunately, Brunhilda does not know the number of children at her party yet. Now, for ~Q~ different numbers ~n_1, \dots, n_Q~ of children, Wotan wants to know in advance the least number of calls he will need to end the game.

Constraints

~1 \le m, Q \le 10^5~

~2 \le p_i \le 10^7~

~1 \le n_j \le 10^7~

Subtask 1 [20%]

~1 \le m, n_j, Q \le 10^4~

Subtask 2 [20%]

~Q = 1~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains two space-separated integers ~m~ and ~Q~.

The second line contains ~m~ different prime numbers ~p_i~ ~(1 \le i \le m)~ in ascending order: the list of prime numbers Wotan can use.

The following ~Q~ lines contain one integer ~n_j~ ~(1 \le j \le Q)~ each: the number of children who might take part in the game.

Output Specification

The output should consist of ~Q~ lines. The ~j^\text{th}~ line should contain the answer for ~n_j~: if Wotan can end the game it should contain the least number of calls he needs (an integer); otherwise, the line should contain the string oo (~\infty~).

Sample Input

2 2
2 3
5
6

Sample Output

3
oo