Overview

We maintain the number of mismatches for every pair of ciphertext and plaintext \((i,j)\) and every shift amount \(r\).
For each query, we perform a differential update on only the affected mismatch counts, then for each shift amount, we find the minimum weight matching using bitmask DP.

Analysis

Let the number of mismatches when comparing ciphertext \(i\) with plaintext \(j\) at shift amount \(r\) be

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

This value counts, only for positions \(p\) where

\[ C_i[p] = 0 \]

(i.e., positions that are readable), the number of positions where

\[ S_i[p] \neq T_j[(p+r) \bmod M] \]

Here, positions are considered \(0\)-indexed in the implementation.

---

For a fixed shift amount \(r\), what we need to do is:

• For ciphertexts \(1,2,\dots,N\)
• Assign plaintexts \(1,2,\dots,N\) without duplication
• Minimize the total cost of the assignment

In other words, this is an assignment problem on the \(N \times N\) cost table \(cost[i][j][r]\).

Since \(N \leq 5\) is very small, this can be solved sufficiently fast with bitmask DP.

---

If we naively check for each query:

• All shift amounts \(r\)
• All correspondences
• All character positions

each query becomes quite expensive.

In particular, recomputing the mismatch counts from scratch each time means repeating the same comparisons many times.

Therefore, we maintain

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

in an always up-to-date state.

When only one character changes, the change affects only some of the \(cost\) values.
For each query, we update only the differences in \(O(NM)\) time.

Algorithm

1. Maintain a mismatch count table

We maintain the following 3-dimensional array:

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

This is the number of mismatches when ciphertext \(i\) is matched with plaintext \(j\) at shift amount \(r\).

In the initial state, we compute this by actually comparing the strings for all \(i,j,r\).

---

2. Compute the answer

For each shift amount \(r\), we find the minimum cost assignment.

We use bitmask DP.

Let

\[ dp[mask] \]

be “the minimum cost when the set of already assigned plaintexts is mask.”

If the number of set bits in mask is \(k\), then the next ciphertext to assign is the \(k\)-th one.

The transition is: choose an unused plaintext \(j\), and

\[ dp[mask \cup \{j\}] = \min( dp[mask \cup \{j\}], dp[mask] + cost[k][j][r] ) \]

Finally,

\[ dp[(1<<N)-1] \]

is the minimum cost for shift amount \(r\).

We compute this for all \(r\) and take the minimum as the answer.

---

3. Query processing

Query 1: 1 i p x

The character \(S_i[p]\) of the ciphertext changes.

If this position is unreadable, i.e., \(C_i[p]=1\), then it is not a comparison target and \(cost\) does not change.

If it is readable, for each plaintext \(j\) and each shift amount \(r\), it is compared with

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

Let the character before the change be old, the character after the change be new, and the character being compared against be ch:

• If ch == old, it was matching before but becomes a mismatch after the change, so \(+1\)
• If ch == new, it was a mismatch before but becomes matching after the change, so \(-1\)
• Otherwise, it remains a mismatch, so no change

We perform the differential update accordingly.

---

Query 2: 2 i p b

The noise information \(C_i[p]\) changes.

If it changes from 1 to 0, meaning the position becomes newly readable, we add the comparison result at that position to \(cost\).

Conversely, if it changes from 0 to 1, meaning the position becomes unreadable, we subtract the comparison result at that position from \(cost\).

For each plaintext \(j\) and each shift amount \(r\), if

\[ S_i[p] \neq T_j[(p+r) \bmod M] \]

then we add or subtract accordingly.

---

Query 3: 3 j p x

The character \(T_j[p]\) of the plaintext changes.

This character, at shift amount \(r\), is compared with the ciphertext position

\[ q = (p-r) \bmod M \]

Therefore, for each ciphertext \(i\) and each shift amount \(r\), we compute position \(q\), and if \(C_i[q]=0\), we perform a differential update.

Let the character before the change be old, the character after the change be new, and the ciphertext character being compared against be ch:

• If ch == old, it was matching before but becomes a mismatch after the change, so \(+1\)
• If ch == new, it was a mismatch before but becomes matching after the change, so \(-1\)
• Otherwise, no change

Complexity

• Time complexity:
  Initialization takes \(O(N^2M^2)\)
  For each query, the differential update takes \(O(NM)\), and recomputing the answer takes \(O(MN2^N)\)
  Therefore, the overall complexity is

$\( O(N^2M^2 + Q(MN + MN2^N)) \)$

Since \(N \leq 5\), \(2^N\) is small, and since \(MQ \leq 5 \times 10^4\), this is sufficiently fast.

• Space complexity: \(O(N^2M)\)

Primarily for storing cost[i][j][r].

Implementation Notes

• In the input, C_i[p] uses 0 for readable and 1 for unreadable as stated in the problem.
  In the implementation, for convenience, we store them inverted: 0 becomes 1 and 1 becomes 0.

• Converting characters from a through z to integers \(0\) through \(25\) speeds up comparisons.

• Position calculations with shifts use \(0\)-indexed implementation.
  The plaintext position corresponding to ciphertext position \(p\) is

$\( (p+r) \bmod M \)$

• In Query 3, the ciphertext position corresponding to plaintext position \(p\) is

$\( (p-r) \bmod M \)$

In the code, by decrementing the position by 1 for each increment of \(r\), we avoid computing the modulus each time.

• Since the bitmask DP transition has the same form every time, pre-enumerating “the transitions used at the stage of assigning ciphertext \(i\)” can make the implementation slightly faster.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())

    S = []
    R = []
    for _ in range(N):
        S.append([c - 97 for c in input().strip()])
        R.append([1 if c == 48 else 0 for c in input().strip()])

    T = [[c - 97 for c in input().strip()] for _ in range(N)]

    cost = [[[0] * M for _ in range(N)] for __ in range(N)]

    doubled_T = [t + t for t in T]
    for i in range(N):
        si = S[i]
        read_pos = [p for p, v in enumerate(R[i]) if v]
        for j in range(N):
            td = doubled_T[j]
            arr = cost[i][j]
            for r in range(M):
                cnt = 0
                for p in read_pos:
                    if si[p] != td[p + r]:
                        cnt += 1
                arr[r] = cnt

    full = 1 << N
    full_mask = full - 1

    popcnt = [0] * full
    for mask in range(1, full):
        popcnt[mask] = popcnt[mask >> 1] + (mask & 1)

    trans_by_i = []
    for i in range(N):
        trans = []
        for mask in range(full):
            if popcnt[mask] == i:
                rem = full_mask ^ mask
                while rem:
                    lb = rem & -rem
                    j = lb.bit_length() - 1
                    trans.append((mask, mask | lb, j))
                    rem -= lb
        trans_by_i.append(trans)

    INF = 10 ** 9

    def calc_answer():
        ans = INF
        cst = cost
        trans_all = trans_by_i
        last = full - 1
        for r in range(M):
            dp = [INF] * full
            dp[0] = 0
            for i in range(N):
                row = cst[i]
                for mask, nmask, j in trans_all[i]:
                    v = dp[mask] + row[j][r]
                    if v < dp[nmask]:
                        dp[nmask] = v
            if dp[last] < ans:
                ans = dp[last]
        return ans

    out = []

    for _ in range(Q):
        parts = input().split()
        typ = parts[0][0] - 48

        if typ == 1:
            i = int(parts[1]) - 1
            p = int(parts[2]) - 1
            new = parts[3][0] - 97
            old = S[i][p]

            if old != new:
                if R[i][p]:
                    cost_i = cost[i]
                    for j in range(N):
                        arr = cost_i[j]
                        tj = T[j]
                        idx = p
                        for r in range(M):
                            ch = tj[idx]
                            if ch == old:
                                arr[r] += 1
                            elif ch == new:
                                arr[r] -= 1
                            idx += 1
                            if idx == M:
                                idx = 0
                S[i][p] = new

        elif typ == 2:
            i = int(parts[1]) - 1
            p = int(parts[2]) - 1
            new_read = 1 if parts[3][0] == 48 else 0
            old_read = R[i][p]

            if old_read != new_read:
                sp = S[i][p]
                cost_i = cost[i]

                if new_read:
                    for j in range(N):
                        arr = cost_i[j]
                        tj = T[j]
                        idx = p
                        for r in range(M):
                            if sp != tj[idx]:
                                arr[r] += 1
                            idx += 1
                            if idx == M:
                                idx = 0
                else:
                    for j in range(N):
                        arr = cost_i[j]
                        tj = T[j]
                        idx = p
                        for r in range(M):
                            if sp != tj[idx]:
                                arr[r] -= 1
                            idx += 1
                            if idx == M:
                                idx = 0

                R[i][p] = new_read

        else:
            j = int(parts[1]) - 1
            p = int(parts[2]) - 1
            new = parts[3][0] - 97
            old = T[j][p]

            if old != new:
                for i in range(N):
                    arr = cost[i][j]
                    si = S[i]
                    ri = R[i]
                    q = p
                    for r in range(M):
                        if ri[q]:
                            ch = si[q]
                            if ch == old:
                                arr[r] += 1
                            elif ch == new:
                                arr[r] -= 1
                        q -= 1
                        if q < 0:
                            q = M - 1
                T[j][p] = new

        out.append(str(calc_answer()))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.