Problem Background

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

Do not abuse the judging system for this problem. Abuse will result in account suspension.

Problem Description

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

Pero wants to rearrange the balls in the matrix such that all blue balls are in the top-left part and all red balls are in the bottom-right part. More specifically, after rearrangement, there should be no red ball above or to the left of any blue ball.

To achieve this, Pero will perform multiple swaps of adjacent balls. 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 achieve the goal.

Additionally, Pero will perform $Q$ swaps of adjacent balls in the matrix and inquire about the minimum number of swaps needed for the current matrix state after each swap. Help Pero by outputting the minimum number of swaps needed for the initial matrix and after each swap.

Input Format

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

The next two lines each contain a string of length $N$ describing the matrix, where $\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 a swap operation:
- If $t = 1$, it means swapping $(x, y)$ and $(x, y+1)$;
- If $t = 2$, it means swapping $(x, y)$ and $(x+1, y)$.

It is guaranteed that the positions being swapped are within the matrix.

Output Format

Output $(Q+1)$ lines, each representing the minimum number of swaps needed for the initial matrix and after each modification.

Sample Input and Output

Sample Input #1

5 2
CPCPC
PCCPC
1 1 4
1 1 2

Sample Output #1

3
4
5

Sample Input #2

5 0
CPPCC
PPCCP

Sample Output #2

4

Sample Input #3

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

Sample Output #3

8
9
10
10
9
8
7
8

Notes

Sample Explanation

Sample #1 Explanation: For the initial state, you only need to swap $(1,1)$ with $(2,1)$, $(1,3)$ with $(1,4)$, and $(1,4)$ with $(2,4)$.

Data Range

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

见题面 Input 部分

见题面 Output 部分