\(c_x\) を \(Ck+x\equiv 0\bmod M\) を満たす \(0\) 以上 \(K\) 未満の整数 \(k\) の個数とします。また、\(d_x\) を \(x,(x+1) \bmod M,\ldots,(x+d_x - 1)\bmod M \in A\) となる \(N\) 以下の最大の整数 \(d_x\) とします。\(c_x\) はクエリにより不変ですが、\(d_x\) はクエリにより変わります。このとき、求める値は \(\displaystyle \sum_{x=0}^{M-1}c_xd_x\) となります。

この \(d_x \neq 0\) を満たす \(x\) が \(O(N)\) 個であることを用いてクエリ変更前の答えを求めることができます。

また、クエリにより \(d\) の値が変わった際の答えの差分は \(O(1)\) 個の \(c\) の区間和で表すことができます。したがって、座標圧縮をした後に \(c\) の累積和を計算し、それらの差分を計算していけば良いです。

\(A\) として出てくる値を円環上の区間として持ち、区間を管理しつつ差分を計算する実装が比較的楽です。

\(A\) として \(0,1,\ldots,M-1\) が全て出てくる場合に注意してください。この場合差分計算が正しく処理できないので、\(0,1,\ldots,M-1\) が全て出てくる場合・ちょうど \(1\) つの値だけ欠けている場合を前計算するなどでこの問題を回避することができます。