An Animal Contest 4 P2 - Lavish Lights

View as PDF

Submit solution


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 N lights arranged in a row numbered from 1 to N.

To ensure a colourful celebration, the lights have been programmed to turn on with a certain pattern. A light with value ai will only be on at a second which is a multiple of ai. Time starts at second 0.

To test out the function of the lights there are Q scenarios. The i-th scenario asks for the index of the first light from the left that will be off during second ti. If all lights will be on, output -1.

Constraints

1N2105

1Q106

1ai109

0ti109

Input Specification

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

The second line contains N space-separated integers ai.

The next Q lines contain ti.

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

Copy
4 2
2 4 6 8
4
24

Sample Output 1

Copy
3
-1

Explanation for Sample 1

For the first scenario, we can see that 4 is a multiple of 2 and 4 but not 6. Therefore the 3-rd light is the first light from the left that is off.

For the second scenario, we can see that 24 is a multiple of 2, 4, 6, and 8. Therefore, all lights are on and we can output -1.

Sample Input 2

Copy
5 1
72 7 69 4 20
0

Sample Output 2

Copy
-1

Comments

There are no comments at the moment.