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
.
Constraints
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
Comments