题目描述
有一个 $2\times n$ （$2$ 行 $n$ 列）的棋盘，棋盘上每个格子都放着一颗巧克力豆或一颗豌豆。
对于一个初始局面，你可以做若干次交换，每次交换形如：
- 选择两个有公共边的格子，交换这两个格子上的豆子。
你需要使得最终局面中所有的豌豆都在棋盘的左上方。具体来说：
- 对于第一行与第二行：同行中，所有豌豆在巧克力豆的左方（即为一个前缀）。
- 设第一行有 $x$ 个豌豆，第二行有 $y$ 个豌豆，则 $x\ge y$。
设 C 为巧克力豆，P 为豌豆，则以下是一个可能的最终局面：
PPPPC PCCCC
你想要经过若干次交换，使得所有的豌豆都在棋盘的左上方。
有 $q$ 次询问，每次会交换初始状态中相邻格子上的豆子。
你需要在第一次交换前和每次交换后，对于这 $q+1$ 种初始状态，分别求出至少需要多少次交换才能使所有的豌豆都在棋盘的左上方。
输入格式
第一行两个整数 $n,q$。
接下来两行，每行一个长度为 $n$ 的字符串，表示初始状态的棋盘。其中 C 为巧克力豆，P 为豌豆。
接下来 $q$ 行，每行三个整数 $op,x,y$。
- $op=1$：交换 $(x,y)$ 和 $(x,y+1)$ 的豆子。
- $op=2$：交换 $(x,y)$ 和 $(x+1,y)$ 的豆子。
- 保证所在的两个格子存在于棋盘内。
输出格式
输出 $q+1$ 行，表示对于 $q+1$ 种初始状态的答案。
样例数据
样例输入 1
5 2 CPCPC PCCPC 1 1 4 1 1 2
样例输出 1
3 4 5
样例解释 1
对于第一个初始状态，交换 (1,1)-(2,1),(1,3)-(1,4),(1,4)-(2,4).
样例输入/输出 2~8
见下发文件。分别满足 Subtask 1~7 的性质。
数据范围
对于所有数据，$1\le n\le 10^6,0\le q\le 10^6$。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $n\le 10,q\le 10^6$ | $8$ |
| $2$ | 至多有 $10$ 个 C |
$12$ |
| $3$ | $n,q\le 500$ | $16$ |
| $4$ | $n,q\le 5000$ | $12$ |
| $5$ | $n\le 100000,q\le 100$ | $16$ |
| $6$ | 保证所有操作 $op=2$ | $16$ |
| $7$ | 无特殊限制 | $20$ |