Hints: Interval Mod

For a single index, if you could ignore interval-length constraints, what is the smallest value you can reach using only mods by $p$ and $q$? Express it using $a_i \bmod p$ and $(a_i \bmod q) \bmod p$.

Answer to Hint 1: Define

$$ c_0(i)=a_i \bmod p,\quad c_1(i)=(a_i \bmod q) \bmod p,\quad c_{\min}(i)=\min(c_0(i),c_1(i)). $$

If every position could be optimized independently, the baseline sum would be $\sum_i c_{\min}(i)$.

Answer to Hint 2: Any operation uses an interval of length at least $k$. A useful simplification in the model solution is: compare the baseline to what happens if you apply one uniform operation on a single interval of length exactly $k$: either $m=p$ everywhere on that interval, or $m=q$ everywhere on that interval.

Answer to Hint 3: If you choose interval $[i,i+k-1]$ and use $m=p$, then indices in that window contribute $c_0$ instead of $c_{\min}$, and indices outside still contribute $c_{\min}$. The total becomes

$$ \text{base} - \sum_{j=i}^{i+k-1} c_{\min}(j) + \sum_{j=i}^{i+k-1} c_0(j). $$

Similarly, for $m=q$ on the same window, replace the window sum with $\sum c_1$.

Answer to Hint 4: Precompute prefix sums of $c_0$, $c_1$, and $c_{\min}$, slide $i$ from $0$ to $n-k$, and take the minimum of the two window costs over all $i$. The answer is that minimum.

Answer to Hint 5: Complexity is $O(n)$ per test case after $O(n)$ preprocessing; memory $O(n)$.