408815: GYM103328 L Dungeon Matrix

You, an adventurer, found a strange room inside a dungeon.

The room consists of $$$N^2$$$ sculptures of soldiers arranged in an $$$N$$$ by $$$N$$$ square, where each soldier raises either his left hand or his right hand. You noticed that there is a button on the wall. Out of curiosity, you pressed it. Suddenly, $$$N$$$ sculptures in the same row started to move, and all of them changed their raising hands.

After some investigations, you found a message written on the wall below the button. Each line of the message represents a row or a column of the $$$N$$$ by $$$N$$$ square that the soldiers form. The first line of the message is the next changing row or column. That is, every time you press the button, the soldiers in that specific row or column will change the hand they raise. After that, the first line of the message will disappear and the second line will indicate the next event.

You want to find some properties of the soldiers since it might provide you some insights to beat the boss in the dungeon. It occurred to you that you can view the square of soldiers as a matrix, and you can use $$$0$$$ and $$$1$$$ to represent soldiers raising left hands and right hands. Therefore, the square of soldiers becomes a $$$0$$$-$$$1$$$ matrix.

You believe that the rank of a $$$0$$$-$$$1$$$ matrix is the most crucial property, but it turns out that the rank of a $$$0$$$-$$$1$$$ matrix is not symmetric in terms of $$$0$$$ and $$$1$$$. In particular, you're not sure whether it'd be better to use $$$0$$$ for left hands (and thus $$$1$$$ for right hands) or vice versa, and sometimes interchanging the representation results in matrices with different ranks. As a result, instead of a specific representation, you would like to consider both options and calculate the L-rank — the minimum value between the ranks of these two matrices.

Now, you know the first $$$Q$$$ lines of the message on the wall, and you want to calculate the L-rank of the soldier matrix after each of the $$$Q$$$ events.

The first line of the input contains a single integer $$$N$$$ — the size of the soldier matrix.

Each of the next $$$N$$$ lines contains a string of length $$$N$$$ consisting of characters L and R. The $$$j$$$-th character in the $$$i$$$-th line indicates the hand that the soldier in the $$$j$$$-th column of the $$$i$$$-th row is currently raising (L for left hand and R for right hand).

The next line contains a single integer $$$Q$$$ — the number of events. $$$Q$$$ lines follow, and the $$$i$$$-th of which contains a string $$$s_i$$$ and an integer $$$k_i$$$. If $$$s_i$$$ is row, then in the $$$i$$$-th event, the soldiers in the $$$k_i$$$-th row will change their raising hands. If $$$s_i$$$ is col, the soldiers in the $$$k_i$$$-th column will change their raising hands.

• $$$1 \leq N, Q \leq 1000$$$
• $$$1 \leq k_i \leq N$$$

Output $$$Q + 1$$$ lines. The first line should contain the L-rank of the initial soldier matrix. The remaining $$$Q$$$ lines should contain the L-rank after each of the $$$Q$$$ events.

3
RRR
RRR
RRR
2
row 1
col 1

0
1
2

10
RRRRRRRLLL
LLRLLLRLLR
RRLLRLLLLL
LLLLLLLRLL
LRRRLRLRRL
LLLLLRLRRR
RRLRLLLLRR
LLLRLRLLLR
RRRLRRRLLL
LRLRLLLRLR
0

9

The rank of a $$$0$$$-$$$1$$$ matrix is the size of the maximal set $$$S$$$ of rows, such that for every nonempty subset $$$S^\prime$$$ of $$$S$$$, there exists at least one $$$i$$$ such that the sum of the $$$i$$$-th entries of the elements in $$$S^\prime$$$ is odd.

For the first sample case, the two representations of the initial soldier matrix are

$$$$$$ \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \end{pmatrix} $$$$$$

and

$$$$$$ \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} $$$$$$

. The former is of rank $$$1$$$ and the latter is of rank $$$0$$$. Therefore, the L-rank is $$$0$$$. After the first event, the soldiers in the first row change their raising hands, and the two representations become

$$$$$$ \begin{pmatrix} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \end{pmatrix} $$$$$$

and

$$$$$$ \begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} $$$$$$

. Both matrices are of rank $$$1$$$, and thus the L-rank is $$$1$$$ as well. After the second event, the soldiers in the first column change their raising hands, resulting in representations

$$$$$$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \\ \end{pmatrix} $$$$$$

and

$$$$$$ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ \end{pmatrix} $$$$$$

. The L-rank becomes $$$2$$$.