An Animal Contest 4 P2 - Lavish Lights

View as PDF

Submit solution

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

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 a_i will only be on at a second which is a multiple of a_i. 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 t_i. If all lights will be on, output -1.


1 \le N \le 2 \cdot 10^5

1 \le Q \le 10^6

1 \le a_i \le 10^9

0 \le t_i \le 10^9

Input Specification

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

The second line contains N space-separated integers a_i.

The next Q lines contain t_i.

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

Sample Output 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

5 1
72 7 69 4 20

Sample Output 2



There are no comments at the moment.