6291번 - Brunhilda’s Birthday 다국어

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 ∞ 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₁, . . . , n_Q of children, Wotan wants to know in advance the least number of calls he will need to end the game.

The first line contains the integers m and Q described above. The second line contains m different prime numbers p_i (1 ≤ i ≤ m) in ascending order: the list of prime numbers Wotan can use. The following Q lines contain one integer n_j (1 ≤ j ≤ Q) each: the number of children who might take part in the game.

The output should consist of Q lines. The j-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 (two lower case letters o, meaning ∞).

• 1 ≤ m ≤ 100 000
• 1 ≤ Q ≤ 100 000
• 2 ≤ p_i ≤ 10 000 000
• 1 ≤ n_j ≤ 10 000 000