{"raw_statement":[{"iden":"background","content":"译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T2。$\\texttt{5s,512M}$。\n\n**请不要滥用本题评测。滥用本题评测将被封号。**"},{"iden":"statement","content":"\nPero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。\n\nPero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。\n\n为此，Pero 可以多次交换相邻的两个球。**两个球是相邻的当且仅当它们所在的格子有公共边。** Pero 想知道达到目标所需的最少交换次数。\n\n此外，Pero 会交换矩阵中的相邻两个球 $Q$ 次，并在每次变更后询问当前矩阵状态所需的最小交换次数。请帮助 Pero，输出初始矩阵下以及每次交换后所需的最小交换次数。"},{"iden":"input","content":"\n第一行，两个整数 $N,Q$，含义见题面。\n\n接下来两行，每行一个长度为 $N$ 的字符串，描述这个矩阵。其中 $\\texttt{C}$ 代表红球，$\\texttt{P}$ 代表蓝球。\n\n接下来 $Q$ 行，每行三个正整数 $t,x,y$，描述一次交换操作。\n\n- $t=1$ 时，表示交换 $(x,y),(x,y+1)$；\n- $t=2$ 时，表示交换 $(x,y),(x+1,y)$。\n\n保证交换的两个位置都在矩阵内。\n"},{"iden":"output","content":"\n输出 $(Q+1)$ 行，分别表示初始矩阵的答案和每次修改后的答案。\n"},{"iden":"note","content":"\n#### 样例解释\n\n样例 $1$ 解释：对于初始状态，只需要依次交换 $(1,1),(2,1)$，$(1,3),(1,4)$，$(1,4),(2,4)$ 即可。\n\n#### 数据范围\n\n对于 $100\\%$ 的数据，保证 $1\\le N\\le  10^6$，$0\\le Q\\le 10^6$。\n\n| 子任务编号 | 分值 | 约束  |\n|:-----:|:------:|:-------:|\n| $1$  | $7$  | $N\\le 10$   |\n| $2$  | $11$  | 最多只有 $10$ 个 $\\texttt{C}$  |\n| $3$  | $17$  | $N,Q\\le 500$ |\n| $4$  | $10$  | $N,Q\\le 5\\, 000$ |\n| $5$  | $13$  | $N\\le 100\\, 000, Q\\le 100$ |\n| $6$  | $15$  | $t=2$ |\n| $7$  | $27$  | 无额外约束 |\n\n"}],"translated_statement":null,"sample_group":[["5 2\nCPCPC\nPCCPC\n1 1 4\n1 1 2","3\n4\n5"],["5 0\nCPPCC\nPPCCP","4"],["10 7\nCCPPPCCPCP\nPPPCCCPCCC\n1 2 7\n2 1 4\n2 1 8\n1 1 9\n2 1 1\n1 2 7\n1 1 4","8\n9\n10\n10\n9\n8\n7\n8"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}