The annual Christmas light show is happening this weekend! The light show consists of a line of lights arranged in a row numbered from to .
To ensure a colourful celebration, the lights have been programmed to turn on with a certain pattern. A light with value will only be on at a second which is a multiple of . Time starts at second .
To test out the function of the lights there are scenarios. The -th scenario asks for the index of the first light from the left that will be off during second . If all lights will be on, output
The first line contains two space-separated integers, and .
The second line contains space-separated integers .
The next lines contain .
For each scenario, if all the lights are on, output
Otherwise, output the index of the first light off from the left.
Sample Input 1
4 2 2 4 6 8 4 24
Sample Output 1
Explanation for Sample 1
For the first scenario, we can see that is a multiple of and but not . Therefore the -rd light is the first light from the left that is off.
For the second scenario, we can see that is a multiple of , , , and . Therefore, all lights are on and we can output
Sample Input 2
5 1 72 7 69 4 20 0
Sample Output 2