Background

Translated from Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D2T2。$\texttt{5s,512M}$。

Please do not abuse the judge for this problem. If you abuse the judge for this problem, your account will be banned.

Problem Description

Pero has a matrix with $2$ rows and $N$ columns. Each cell contains either a red ball or a blue ball.

Pero wants to rearrange the balls in the matrix so that all blue balls are on the upper-left side of the matrix, and all red balls are on the lower-right side. More specifically, after rearranging, there must not exist a red ball that is above or to the left of some blue ball.

To do this, Pero can swap two adjacent balls multiple times. Two balls are adjacent if and only if the cells they are in share an edge. Pero wants to know the minimum number of swaps needed to reach the goal.

In addition, Pero will perform $Q$ swaps of adjacent balls in the matrix, and after each change, he asks for the minimum number of swaps needed for the current matrix state. Please help Pero output the minimum number of swaps needed for the initial matrix, and after each swap.

Input Format

The first line contains two integers $N,Q$, as described in the statement.

The next two lines each contain a string of length $N$, describing the matrix. $\texttt{C}$ represents a red ball, and $\texttt{P}$ represents a blue ball.

The next $Q$ lines each contain three positive integers $t,x,y$, describing one swap operation.

• When $t=1$, swap $(x,y)$ and $(x,y+1)$.
• When $t=2$, swap $(x,y)$ and $(x+1,y)$.

It is guaranteed that the two swapped positions are both inside the matrix.

Output Format

Output $(Q+1)$ lines, representing the answer for the initial matrix and the answer after each modification.

5 2
CPCPC
PCCPC
1 1 4
1 1 2

3
4
5

5 0
CPPCC
PPCCP

4

10 7
CCPPPCCPCP
PPPCCCPCCC
1 2 7
2 1 4
2 1 8
1 1 9
2 1 1
1 2 7
1 1 4

8
9
10
10
9
8
7
8

Hint

Sample Explanation

Sample $1$ explanation: For the initial state, it is enough to swap $(1,1)$ and $(2,1)$, then swap $(1,3)$ and $(1,4)$, then swap $(1,4)$ and $(2,4)$.

Constraints

For $100\%$ of the data, it is guaranteed that $1\le N\le 10^6$ and $0\le Q\le 10^6$.

Translated by ChatGPT 5