Let ~X~ be the minimum possible number of inactive intervals which the site's maintenance schedule could consist of. Our first order of business will need to be calculating ~X~.

Let's start by sorting all ~N+M~ observed times together in a single list (in ~\mathcal O((N+M) \log(N+M))~ time). Then, ~X~ is simply the number of occurrences of an inactive time directly preceding an active time. Keep in mind that the last time in the list directly precedes the first time as well.

Now, the answer is Impossible if and only if ~I < X~.

Assuming that it's possible, the site's status is known for at least each of the ~N+M~ observed times. The interesting question is, when can the statuses of other times also be inferred? If ~I > X~, then in fact no other statuses can be inferred at all – with even ~1~ extra interval of leeway, the inactive intervals can always be shuffled around to make any other time either active or inactive.

This leaves the case in which ~I = X~. In this situation, each inactive interval is forced to span a certain consecutive interval of observed inactive times, but past that, its starting and ending times may vary up to the previous/next observed active times. The result is that all times between consecutive pairs of observed inactive times are also inactive. Similarly, all times between consecutive pairs of observed active times are also active. However, the statuses of times sandwiched between an observed inactive time and an observed active time remain unknown.

From there, there are several approaches to efficiently processing the queries, in ~\mathcal O(\log(N+M))~ time each. For example, we can binary search for the queried point in the list of ~N+M~ observed times. If it's present, then its status is already known. Otherwise, if ~I = X~, we can look at the previous and next observed times surrounding it and see whether its status can be inferred from theirs.