Let \(c_x\) be the number of integers \(k\) between \(0\) (inclusive) and \(K\) (exclusive) satisfying \(Ck+x\equiv 0\bmod M\). Also, let \(d_x\) be the maximum integer not greater than \(N\) such that \(x,(x+1) \bmod M,\ldots,(x+d_x - 1)\bmod M \in A\). \(c_x\) are constant over the queries, while \(d_x\) are modified by the queries. The sought value is \(\displaystyle \sum_{x=0}^{M-1}c_xd_x\).

We can find the answer before the queries using the property that there are \(O(N)\) indices \(x\) with \(d_x \neq 0\).

Also, when \(d\) is modified by a query, the delta of the answer can be represented as \(O(1)\) segment-sums on \(c\). Therefore, we may apply coordinate compression, calculate the cumulative sums, and find the differences.

As a relatively simple implementation, we may maintain the values occurring in \(A\) as segments on a circumference, and manage the segments while computing the difference.

Note that \(A\) may contain all values \(0,1,\ldots,M-1\). In this case, the difference cannot be handled correctly. One possible approach is to precalculate the answer for the case containing all \(0,1,\ldots,M-1\), and when only one value is missing.