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:
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 |
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:
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:
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 |
After applying the first operation, we get the following matrix with flow $$$3$$$:
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 |
After applying the second operation, we get the following matrix with flow $$$2$$$:
0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 0 |
After applying the third operation, we get the following matrix with flow $$$2$$$:
0 | 0 | 1 | 0 |
1 | 1 | 1 | 1 |
1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 |
After applying the fourth operation, we get the following matrix with flow $$$0$$$:
0 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
0 | 1 | 1 | 1 |
Name |
---|