Solution 1:

We can solve this problem for each query by finding the first prefix LCM ~P~ such that ~P~ does not divide ~t_i~. If such a ~P~ does not exist, that means that all lights are on at time ~t_i~ (~t_i~ is a multiple of all integers in array ~a~), and we can output -1.

To answer these queries efficiently, we can construct a prefix LCM array, stopping when the prefix LCM exceeds the maximum allowed ~t_i~ value, ~10^9~. For each query, we can run binary search and check if ~t_i~ divides all numbers up to some index ~idx~.

Be careful of the case when ~t_i = 0~; ~0~ is a multiple of all integers.

Time Complexity: ~\mathcal{O}(N \log 10^9 + Q \log N)~

Solution 2:

If binary search isn't for you, observe that there are only a maximum of around ~\log 10^9~ positions ~j~ where the light at position ~j~ will be the first to be off. We can find these positions by considering the prefix LCM and then for each query we can run linear search over these positions.

Again, be careful about edge cases such as when ~t_i = 0~.

Time Complexity: ~\mathcal{O}(N \log 10^9 + Q \log 10^9)~

It is even possible to perform binary search instead of linear search in solution 2 to achieve a complexity of ~\mathcal{O}(N \log 10^9 + Q \log \log 10^9)~.