Overview

For each ciphertext \(i\) and each plaintext \(j\), we precompute and maintain the number of mismatches for each shift amount \(r\).
For update queries, we only perform a differential update on the effect of the single changed character (or single mask position), and then try all shift amounts and all assignments to find the minimum.

Analysis

Consider maintaining the number of mismatches when comparing ciphertext \(i\) with plaintext \(j\) at shift amount \(r\) as:

\[ cost[i][j][r] \]

Using 0-indexed notation, position \(p\) in the ciphertext corresponds to position

\[ (p+r) \bmod M \]

in the plaintext.

Therefore,

\[ cost[i][j][r] = \sum_{p=0}^{M-1} [C_i[p]=\texttt{0}] [S_i[p] \ne T_j[(p+r)\bmod M]] \]

Here, \([condition]\) denotes \(1\) if the condition is true and \(0\) if false.

---

For a fixed shift amount \(r\), we need to decide which plaintext to assign to each ciphertext \(i\).
This is a problem of determining \(N\) assignments, but since the constraint is

\[ N \leq 5 \]

we can try all permutations.

Thus, the answer is

\[ \min_{0 \leq r < M} \min_{\pi} \sum_{i=0}^{N-1} cost[i][\pi(i)][r] \]

---

If we naively compare all shift amounts, all assignments, and all character positions after each query, the complexity would be

\[ O(Q \cdot M \cdot N! \cdot N \cdot M) \]

which is far too slow.

Instead, we maintain the mismatch count cost for each pair and each shift amount.
Since a single update changes only one character or one mask position, it suffices to differentially update only the cost entries affected by that position.

Algorithm

1. Compute the initial cost

For all \(i, j, r\), examine all positions \(p\) and count mismatches.

for i
  for j
    for r
      for p
        if C[i][p] == '0' and S[i][p] != T[j][(p+r)%M]
          cost[i][j][r]++

2. Enumerate all permutations for plaintext assignment

Since \(N \leq 5\), there are at most

\[ 5! = 120 \]

permutations.

For a permutation p, we assign plaintext p[i] to ciphertext \(i\).

3. Compute the answer

For each shift amount \(r\) and each permutation p, compute

\[ \sum_i cost[i][p[i]][r] \]

and take the minimum as the answer.

4. Query processing

Query 1: 1 i p x

Change the character \(S_i[p]\) in the ciphertext.

This change only affects comparisons involving position \(p\) of ciphertext \(i\).
However, if \(C_i[p]=\texttt{1}\), that position is excluded from comparison, so cost does not change.

When \(C_i[p]=\texttt{0}\), for all plaintexts \(j\) and shift amounts \(r\), let

\[ tp = (p+r) \bmod M \]

and update:

\[ cost[i][j][r] \mathrel{+}= [x \ne T_j[tp]] - [old \ne T_j[tp]] \]

Query 2: 2 i p b

Change the mask \(C_i[p]\).

When changing from 1 to 0, the position newly becomes a comparison target, so add \(+1\) if there is a mismatch.
When changing from 0 to 1, the position is removed from comparison, so subtract \(-1\) if there is a mismatch.

Let oldActive = 1 if the position was a comparison target under the old state, 0 otherwise, and define newActive similarly for the new state. Then:

\[ cost[i][j][r] \mathrel{+}= (newActive - oldActive) \cdot [S_i[p] \ne T_j[(p+r)\bmod M]] \]

Query 3: 3 j p x

Change the character \(T_j[p]\) in the plaintext.

We compute which ciphertext position corresponds to plaintext position \(p\) at shift amount \(r\):

\[ sp = (p-r+M) \bmod M \]

Therefore, for all ciphertexts \(i\) and shift amounts \(r\), only when \(C_i[sp]=\texttt{0}\), update:

\[ cost[i][j][r] \mathrel{+}= [S_i[sp] \ne x] - [S_i[sp] \ne old] \]

Complexity

• Time complexity: \(O(N^2M^2 + Q(NM + MN!N))\)
  • Initial cost computation: \(O(N^2M^2)\)
  • Differential update per query: \(O(NM)\)
  • Answer computation per query: \(O(MN!N)\)
• Space complexity: \(O(N^2M + N!N)\)

Since \(N \leq 5\) and \(M Q \leq 5 \times 10^4\), this is fast enough.

Implementation Notes

• The input is 1-indexed, but converting to 0-indexed in the implementation makes things easier to handle.

• When comparing with shift amount \(r\), the plaintext position corresponding to ciphertext position \(p\) is (p + r) % M.

• For queries that modify the plaintext, think in reverse: the corresponding ciphertext position is found as (p - r + M) % M.

• Update cost before modifying the actual strings S, C, T, since we need the difference between the old and new values.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<string> S(N), C(N), T(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        cin >> C[i];
    }
    for (int j = 0; j < N; j++) cin >> T[j];

    vector<vector<vector<int>>> cost(N, vector<vector<int>>(N, vector<int>(M, 0)));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int r = 0; r < M; r++) {
                int cnt = 0;
                for (int p = 0; p < M; p++) {
                    if (C[i][p] == '0' && S[i][p] != T[j][(p + r) % M]) {
                        cnt++;
                    }
                }
                cost[i][j][r] = cnt;
            }
        }
    }

    vector<vector<int>> perms;
    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 0);
    do {
        perms.push_back(perm);
    } while (next_permutation(perm.begin(), perm.end()));

    auto answer = [&]() -> int {
        int ans = INT_MAX;
        for (int r = 0; r < M; r++) {
            for (const auto& p : perms) {
                int sum = 0;
                for (int i = 0; i < N; i++) {
                    sum += cost[i][p[i]][r];
                }
                ans = min(ans, sum);
            }
        }
        return ans;
    };

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int i, p;
            char x;
            cin >> i >> p >> x;
            --i;
            --p;

            char old = S[i][p];
            if (old != x && C[i][p] == '0') {
                for (int j = 0; j < N; j++) {
                    for (int r = 0; r < M; r++) {
                        int tp = (p + r) % M;
                        int before = (old != T[j][tp]);
                        int after = (x != T[j][tp]);
                        cost[i][j][r] += after - before;
                    }
                }
            }
            S[i][p] = x;
        } else if (type == 2) {
            int i, p;
            char b;
            cin >> i >> p >> b;
            --i;
            --p;

            char old = C[i][p];
            if (old != b) {
                int oldActive = (old == '0');
                int newActive = (b == '0');
                for (int j = 0; j < N; j++) {
                    for (int r = 0; r < M; r++) {
                        int tp = (p + r) % M;
                        int mis = (S[i][p] != T[j][tp]);
                        cost[i][j][r] += (newActive - oldActive) * mis;
                    }
                }
            }
            C[i][p] = b;
        } else {
            int j, p;
            char x;
            cin >> j >> p >> x;
            --j;
            --p;

            char old = T[j][p];
            if (old != x) {
                for (int i = 0; i < N; i++) {
                    for (int r = 0; r < M; r++) {
                        int sp = (p - r + M) % M;
                        if (C[i][sp] == '0') {
                            int before = (S[i][sp] != old);
                            int after = (S[i][sp] != x);
                            cost[i][j][r] += after - before;
                        }
                    }
                }
            }
            T[j][p] = x;
        }

        cout << answer() << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.