Problem Statement

Takahashi has received N encrypted messages. Each encrypted message is a string of length M consisting of lowercase English letters, but due to noise during transmission, some positions have become unreadable, and even the readable positions may contain errors.

Meanwhile, N original plaintext strings of length M are given, which are supposed to be the sources of these encrypted messages. It is believed that during encryption, all plaintexts were cyclically shifted by a common shift amount to produce the encrypted messages, but neither the exact shift amount nor the correspondence between encrypted messages and plaintexts is known.

Takahashi wants to find the shift amount and correspondence that minimize the total number of mismatches.

Definitions

Each position in a string is represented by an integer from 1 to M.

Cyclic shift and position correspondence: Comparing an encrypted message with a plaintext using shift amount r (an integer with 0 \leq r < M) means comparing the encrypted message with the string obtained by cyclically shifting the plaintext r characters to the left, at corresponding positions. Specifically, the plaintext position corresponding to position p in the encrypted message is ((p + r - 1) \bmod M) + 1.

Noise information: Each encrypted message i (1 \leq i \leq N) is paired with a received string S_i and a readability string C_i. If position p of C_i is 0, then the character at that position is readable and is subject to comparison. If it is 1, it means that position was unreadable and is excluded from comparison.

Number of mismatches: The number of mismatches when pairing encrypted message i with plaintext j using shift amount r is defined as follows. For all positions p (1 \leq p \leq M) where position p of C_i is 0, compare the character at position p of S_i with the character at position ((p + r - 1) \bmod M) + 1 of T_j. The number of positions where they differ is the number of mismatches.

Objective

Choose one shift amount r (0 \leq r < M), and determine a one-to-one correspondence between the N encrypted messages and the N plaintexts (i.e., assign one plaintext to each of encrypted messages 1, 2, \ldots, N without repetition). The shift amount r is common to all correspondence pairs.

Consider the total number of mismatches across all correspondence pairs, and find its minimum value.

Update Queries

Q updates are applied sequentially to the encrypted messages or plaintexts. After each update, find the above minimum value for the current state.

Constraints

• 1 \leq N \leq 5
• 1 \leq M \leq 500
• 1 \leq Q \leq 500
• M Q \leq 5 \times 10^4
• S_i is a string of length M consisting of lowercase English letters (1 \leq i \leq N)
• C_i is a string of length M consisting of 0 and 1 (1 \leq i \leq N)
• T_j is a string of length M consisting of lowercase English letters (1 \leq j \leq N)
• Each update query is one of the following three types:
• Format 1 i p x: 1 \leq i \leq N, 1 \leq p \leq M, x is a lowercase English letter
• Format 2 i p b: 1 \leq i \leq N, 1 \leq p \leq M, b is 0 or 1
• Format 3 j p x: 1 \leq j \leq N, 1 \leq p \leq M, x is a lowercase English letter

Sample Input 1

2 4 5
abca
0000
zzzz
1010
bcaa
zzzz
1 1 2 c
2 2 1 0
3 1 4 b
2 1 3 1
1 2 4 a

Sample Output 1

1
1
2
2
3

Sample Input 2

1 5 4
abcde
00101
cdeab
3 1 1 a
2 1 3 0
1 1 5 b
3 1 4 z

Sample Output 2

0
1
1
2

Sample Input 3

3 8 10
abcdefgh
00001111
hgfedcba
01010101
aaaabbbb
11110000
cdefghab
fedcbahg
bbbbaaaa
1 1 4 z
2 3 2 0
3 2 8 a
1 2 1 f
2 1 5 0
3 1 3 x
2 2 4 0
1 3 8 c
3 3 5 z
2 1 1 1

Sample Output 3

3
3
3
4
4
5
5
5
5
5

Sample Input 4

5 20 15
abcdefghijklmnopqrst
00000000000000000000
zyxwvutsrqponmlkjihg
01010101010101010101
aaaaaaaaaabbbbbbbbbb
11111000001111100000
qwertyuiopasdfghjklz
00110011001100110011
mnopqrstuvwxyzabcdef
10000000000000000001
defghijklmnopqrstabc
ghijklmnopqrstuvwxyz
bbbbbbbbbbaaaaaaaaaa
poiuytrewqlkjhgfdsaz
nopqrstuvwxyzabcdefg
1 1 20 a
2 2 2 0
3 3 10 c
1 4 5 z
2 5 1 0
3 1 1 q
1 3 11 a
2 4 19 1
3 5 20 y
1 2 7 b
2 1 10 1
3 4 4 a
1 5 14 m
2 3 6 1
3 2 15 d

Sample Output 4

41
42
42
42
42
42
42
42
42
42
41
41
42
42
43

Sample Input 5

1 1 5
a
0
b
3 1 1 a
1 1 1 z
2 1 1 1
3 1 1 z
2 1 1 0

Sample Output 5

0
1
0
0
0