409480: GYM103577 F Flow of binary matrix

A binary matrix is a matrix that has either $$$0$$$ or $$$1$$$ in all of its cells. The flow of a binary matrix is the number of rows contain only $$$1$$$'s plus the number of columns that contain only $$$1$$$'s, for example, here is a matrix with flow 3:

The flow is $$$3$$$ because row $$$2$$$ and columns $$$1$$$ and $$$4$$$ are full of $$$1$$$s.

You are given a binary matrix of size $$$n \times n$$$, and you have to write a program to perform several operations, and for each operation your program must output the flow of the matrix after applying the operation. There are two types of operations:

• 1 i j b — updates the value in the $$$i$$$-th row and the $$$j$$$-th column to be equal to $$$b$$$ ($$$1 \leq i, j \leq n$$$ and $$$b$$$ is either $$$0$$$ or $$$1$$$).
• 2 b — inserts the value $$$b$$$ ($$$b$$$ is either $$$0$$$ or $$$1$$$) in the matrix at position $$$(1,1)$$$, this moves all values of the first row $$$1$$$ column to the right, the last element of the first row is removed from the first row and inserted as the first element of the second row, causing a cascade behavior that ends up in the last row having $$$n+1$$$ elements. The last value of the $$$n$$$-th row is discarded and the matrix will still have dimensions $$$n \times n$$$.

The first line of input contains two space separated integers: $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 5000$$$ and $$$1 \leq q \leq 5000$$$).

The next $$$n$$$ lines describe the binary matrix. The $$$j$$$-th character of the $$$i$$$-th line is the value of the binary matrix at position $$$(i,j)$$$.

The next $$$q$$$ lines each contain an operation. The operations follow the format described in the statement.

$$$q$$$ lines, the $$$i$$$-th line must contain the flow of the binary matrix after applying the $$$i$$$-th operation.

4 4
1011
1111
1101
1101
1 3 2 0
2 0
2 0
1 2 3 0

3
2
2
0

This is the initial matrix:

After applying the first operation, we get the following matrix with flow $$$3$$$:

After applying the second operation, we get the following matrix with flow $$$2$$$:

After applying the third operation, we get the following matrix with flow $$$2$$$:

After applying the fourth operation, we get the following matrix with flow $$$0$$$: