If \(A = B\)

Obviously, it is necessary that \(1 \equiv N \pmod A\).

If \(1 \equiv N \pmod A\), you visit squares \(1, A + 1, 2A + 1, \ldots, N - A, N\), so it is sufficient to check if there exists an \(x\) with \(1 \equiv x \pmod A\) such that square \(x\) is bad. This can be determined by checking for each \(i\) if there exists a \(j\) with \(L_i \leq j \leq R_i\) and \(1 \equiv j \pmod A\), which can be done in \(O(M)\) time.

If \(A < B\)

As there are \(N\) squares, we cannot check the reachability for all the squares; instead, we speed it up by inspecting only some of them.

Define length-\((M + 1)\) sequences \(S\) and \(T\) by:

• \(S_1 = 1\),
• \(S_i = R_{i - 1} + 1\) \((i > 1)\),
• \(T_i = L_i - 1\) \((i \leq M)\),
• \(T_{M + 1} = N\).

Also, define a sequence \(I_i\) as \((S_i, S_i + 1, \ldots, T_i)\).

Let \(X_i\) be the first \(B\) terms of \(I_i\), and \(Y_i\) be the last \(B\) terms. If the length of \(I_i\) is less than \(B\), let \(X_i = Y_i = I_i\).

The sum of lengths of \(X_i\) and \(Y_i\) is \(O(MB)\); we aim to check the reachability for those squares.

When we know the reachability for those in \(X_1, X_2, \ldots, X_i\) and \(Y_1, Y_2, \ldots, Y_i\), we can easily determine the reachability for those in \(X_{i + 1}\) in \(O(B^2)\) time by inspecting the first \(B\) squares.

Now we will try to find the reachability for those in \(Y_i\) when we know that for \(X_1, X_2, \ldots, X_i\) and \(Y_1, Y_2, \ldots, Y_{i - 1}\). This can be done by first checking the reachability to the first \(B\) squares just as above, and then that from each square in \(X_i\) via one or more moves. (The cases where you jump over one or more squares is covered by the former, and the others by the latter.)

Therefore, if one can determine if one can advance \(w\) squares when there are no bad squares in between, then it can also be processed in \(O(B^2)\) time.

By \(A < B\), we can advance \(B - 1\) or \(B\) squares in one move, so we can advance \(w\) squares for all \(w \geq B^2-3B + 2\). For \(w < B^2-3B + 2\), we can precalculate the reachability with naive DP (Dynamic Programming) in \(O(B^3)\) time.

Therefore, the entire process completes in \(O(MB^2 + B^3)\) time. On actual implementation, we may also adopt an \(\Theta(MB^2 + MB \log(MB) + B^3)\) solution using sets or maps. We have also asserted that \(\Theta(MB^2 \log(MB) + B^3)\) also passes, as long as the constant factor is not very large.