First, we consider the sufficient and necessary conditions that a sequence \(X = (X_1, X_2, \ldots, X_n)\) is a good sequence.

Let \(X_0 \coloneqq 0\) and \(X_{n+1} \coloneqq 0\), and consider the sequence \(X' = (X'_0, X'_1, \ldots, X'_n)\) that is a sequence of differences of \((X_0, X_1, X_2, \ldots, X_n, X_{n+1})\), where \(X'_i = X_{i+1} - X_i\). Then, adding an integer \(c\) to consecutive \(K\) elements of \(X\), making \(X\)

\[(X_0, X_1, \ldots, X_{i-1}, \red{X_i+c, X_{i+1}+c, \ldots, X_{i+K-1}+c}, X_{i+K}, \ldots, X_n, X_{n+1}),\]

corresponds to making the corresponding sequence \(X'\)

\[ (X'_0, X'_1, \ldots, \red{X'_{i-1} + c}, X'_i, X'_{i+1}, \ldots, \red{X'_{i+K-1}-c}, X'_{i+K}, \ldots, X'_n);\]

in other words, it corresponds to adding \(c\) to \(X'_{i-1}\) and \(X'_{i+K-1}\) to \(-c\). Also, the elements of \(X\) is all \(0\) if and only if the elements of \(X'\) are all \(0\). Therefore, \(X\) is a good sequence if and only if one can make all the elements of \(X'\) \(0\) by repeating the following operation:

\((\star)\) choose an integer \(i\) such that \(0 \leq i \leq n-K\) and an integer \(c\) to add \(c\) to \(X'_i\) and \(-c\) to \(X'_{i+K}\).

Here, split the elements of \(X'\) into \(K\) group by the remainders of the indices divided by \(K\). By repeating the operation above (\(\star\)), for each \(r = 0, 1, \ldots, K-1\), the elements \(X'_r, X'_{K+r}, X'_{2K+r}, \ldots, X'_{h_rK+r}\) in the group corresponding to a remainder \(r\) (where \(h_r \coloneqq \lfloor \frac{n-r}{K} \rfloor\)) can be modified freely, as long as the sum \(\sum_{i = 0} ^{h_r} X'_{iK+r}\) remains invariant.

Thus, the elements of \(X'\) can be made \(0\) (i.e. \(X\) is a good sequence) if and only if \(\sum_{i = 0} ^{h_r} X'_{iK+r} = 0\) for all remainders \(r = 0, 1, \ldots, K-1\).

Therefore, one can determine if a given sequence \(X\) is a good sequence by splitting into groups the elements of the sequence of differences \(X'\) by the remainders when the indices are divided by \(K\) and checking if the sum of the elements in every group is \(0\).

However, naively checking in this way for each \((l_i, r_i)\) given in the input costs \(\Theta(N)\) time at worst \(\Theta(N)\) time, for a total of \(\Theta(QN)\) time, which is very unlikely to fit in the time limit. So we optimize it by the following procedure:

• First, for the sequence \(A\) given in the input, find the sequence of differences \(A' = (A'_0, A'_1, \ldots, A'_N)\) of \((A_0, A_1, A_2, \ldots, A_N, A_{N+1})\), where \(A_0 \coloneqq 0, A_{N+1} \coloneqq 0\), and \(A'_i = A_{i+1} - A_i\).

• Next, split the elements of \(A'\) into groups by the remainders when the indices are divided by \(K\), and find the sequence \(S = (S_0, S_1, \ldots, S_N)\) of cumulative sums of each group, that is, the sequence \(S\) defined by \(S_i \coloneqq A'_r + A'_{K+r} + \cdots + A'_{i-r} + A'_i\). It can be found in a total of \(O(N)\) time, using the property that \(S_i = S_{i-r} + A'_i\).

• Then, we determine if each of the given subarrays \((A_l, A_{l+1}, \ldots, A_r)\) is a good sequence using the precomputed cumulative sum array \(S\). The sequence of differences \(X'\) of \((X_0, X_1, \ldots, X_n, X_{n+1}) \coloneqq (0, A_l, A_{l+1}, \ldots, A_r, 0)\) is \((X'_0, X'_1, \ldots, X'_n) = (A'_{l-1}\red{+A_{l-1}}, A'_l, \ldots, A'_r\red{ - A_{r+1}})\). Note that this is almost \((A'_{l-1}, A'_l, \ldots, A'_r)\). For each \(r = 0, 1, \ldots, K-1\), the sum in the form of \(A'_{aK+r} + A'_{(a+1)K+r} + \cdots + A'_{bK+r}\) can be found as \(S_{bK+r} - S_{(a-1)K+r}\) using the precomputed cumulative sum array \(S\), so whether \(\sum_{i = 0} ^{h_r} X'_{iK+r} = 0\) holds can be found in an \(O(1)\) time for each \(r = 0, 1, \ldots, K-1\), so we can determine if \((A_l, A_{l+1}, \ldots, A_r)\) is good in a total of \(O(K)\) time.

Therefore, the problem can be solved in a total of \(O(N + QK)\) time.