Description

The cows want to paint a large picture on an $R \times C$ grid ($1 \le R \le 50{,}000$, $1 \le C \le 15$). Each cell holds a bit, either 0 or 1. Rows are numbered $1..R$, and columns are numbered $1..C$. The initial picture is all 0s.

They will perform $Q$ operations ($1 \le Q \le 10{,}000$). Each operation takes five parameters $R1_i,R2_i,C1_i,C2_i,X_i$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_i \le 1)$, and paints every cell in rows $R1_i$ to $R2_i$ and columns $C1_i$ to $C2_i$ to color $X_i$.

A target image is given as an $R \times C$ grid of '0'/'1' characters. After each operation, output how many cells in the current painted grid match the corresponding cells in the target image.

Memory limit: 64 MB. Time limit: 1.5 seconds.

Input Format

• Line 1: Three space-separated integers: $R$, $C$, and $Q$.
• Lines 2..$R+1$: Line $i+1$ contains $C$ characters, each '0' or '1', denoting the $i$-th row of the target grid.
• Lines $R+2..R+Q+1$: Line $R+i+1$ contains five space-separated integers representing a paint operation: $R1_i$, $R2_i$, $C1_i$, $C2_i$, and $X_i$.

Output Format

• Lines 1..$Q$: On line $i$, print a single integer representing the number of matching unit squares after the $i$-th operation.

17 15 10 
111111101111111 
111111000111111 
111110000011111 
111100000001111 
111000000000111 
111100000001111 
111000000000111 
110000000000011 
111000000000111 
110000000000011 
100000000000001 
110000000000011 
100000000000001 
000000000000000 
111111000111111 
111111000111111 
111111000111111 
5 8 2 14 1 
8 17 3 7 1 
4 5 10 15 0 
7 16 12 14 1 
2 17 13 14 0 
2 6 2 3 1 
13 14 4 8 1 
3 6 6 7 1 
1 16 10 11 0 
7 16 10 10 0 

113 
94 
95 
91 
87 
93 
91 
87 
93 
93 

Hint

The cows want to paint a picture of a holiday tree.

After the first operation, the picture grid looks as follows:

000000000000000

000000000000000

000000000000000

000000000000000

011111111111110

011111111111110

011111111111110

011111111111110

000000000000000

000000000000000

000000000000000

000000000000000

000000000000000

000000000000000

000000000000000

000000000000000

000000000000000

There are 113 unit squares which match the corresponding square in the tree image; they are denoted below by an 'x' (the other bits are shown as they appear after the first paint splash):

0000000x0000000

000000xxx000000

00000xxxxx00000

0000xxxxxxx0000

0xx111111111xx0

0xxx1111111xxx0

0xx111111111xx0

0x11111111111x0

000xxxxxxxxx000

00xxxxxxxxxxx00

0xxxxxxxxxxxxx0

00xxxxxxxxxxx00

0xxxxxxxxxxxxx0

xxxxxxxxxxxxxxx

000000xxx000000

000000xxx000000

000000xxx000000.

Translated by ChatGPT 5