An Animal Contest 4 P2 - Lavish Lights

View as PDF

Points: 10
Time limit: 1.0s
Python 2.0s
Memory limit: 256M

Author:
Problem type

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 -1.

Input Specification

The first line contains two space-separated integers, and .

The second line contains space-separated integers .

The next lines contain .

Output Specification

For each scenario, if all the lights are on, output -1.

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

3
-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 -1.

Sample Input 2

5 1
72 7 69 4 20
0

Sample Output 2

-1