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 is announced. Then all children try to form groups of exactly people. As long as at least children are left over, further groups of children are formed. In the end, less than 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 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 different numbers of children, Wotan wants to know in advance the least number of calls he will need to end the game.
Constraints
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line contains two space-separated integers and .
The second line contains different prime numbers in ascending order: the list of prime numbers Wotan can use.
The following lines contain one integer each: the number of children who might take part in the game.
Output Specification
The output should consist of lines. The line should contain the answer for : 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
().
Sample Input
2 2
2 3
5
6
Sample Output
3
oo
Comments