题目背景

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

请不要滥用本题评测。滥用本题评测将被封号。

题目描述

Pero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。

Pero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。

为了实现这个目标，Pero 会多次交换相邻的两个球。两个球是相邻的当且仅当它们所在的格子有公共边。 Pero 想知道达到目标所需的最少交换次数。

此外，Pero 会交换矩阵中的相邻两个球 $Q$ 次，并在每次变更后询问当前矩阵状态所需的最小交换次数。请帮助 Pero，输出初始矩阵下以及每次交换后所需的最小交换次数。

输入格式

第一行，两个整数 $N,Q$，含义见题面。

接下来两行，每行一个长度为 $N$ 的字符串，描述这个矩阵。其中 $\texttt{C}$ 代表红球，$\texttt{P}$ 代表蓝球。

接下来 $Q$ 行，每行三个正整数 $t,x,y$，描述一次交换操作。

• $t=1$ 时，表示交换 $(x,y),(x,y+1)$；
• $t=2$ 时，表示交换 $(x,y),(x+1,y)$。

保证交换的两个位置都在矩阵内。

输出格式

输出 $(Q+1)$ 行，分别表示初始矩阵的答案和每次修改后的答案。

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

提示

样例解释

样例 $1$ 解释：对于初始状态，只需要依次交换 $(1,1),(2,1)$，$(1,3),(1,4)$，$(1,4),(2,4)$ 即可。

数据范围

对于 $100\%$ 的数据，保证 $1\le N\le 10^6$，$0\le Q\le 10^6$。