Pero 拥有一个两行 $N$ 列的矩阵。矩阵的每个格子中都有一颗红色或蓝色的球。
Pero 的目标是重新排列矩阵中的球，使得所有的蓝色球都位于“左上角”，而所有的红色球都位于“右下角”。更准确地说，重新排列后，不存在任何一颗红色球位于某颗蓝色球的上方或左侧。
为了达到目标，Pero 可以进行若干次操作，每次操作可以交换任意两个相邻球的位置。如果两个格子共享一条边，则称其中的球是相邻的。Pero 想知道达到目标状态所需的最少交换次数。
此外，Pero 会进行 $Q$ 次操作，每次操作都会交换矩阵中两个相邻球的位置。他想在每次交换后知道当前状态下达到目标所需的最少交换次数。请帮助 Pero，并输出初始矩阵以及每次交换后的答案。
输入格式
第一行包含两个整数 $N$ 和 $Q$，分别表示矩阵的列数和 Pero 进行的交换次数。
接下来的两行描述了 Pero 的矩阵。每一行包含 $N$ 个字符，'C' 表示红色球，'P' 表示蓝色球。
接下来的 $Q$ 行，每行包含三个整数 $t, x, y$ ($1 \le t \le 2, 1 \le x \le 2, 1 \le y \le N$)，表示依次进行的交换操作。如果 $t = 1$，则交换相邻格子 $(x, y)$ 和 $(x, y + 1)$ 中的球；如果 $t = 2$，则交换相邻格子 $(x, y)$ 和 $(x + 1, y)$ 中的球。保证这两个格子都在矩阵范围内。
输出格式
输出 $Q + 1$ 行。依次为 $i = 0, 1, \dots, Q$ 时，在 $i$ 次交换后达到目标状态所需的最少交换次数。
子任务
在所有子任务中，满足 $1 \le N \le 10^6$ 且 $0 \le Q \le 10^6$。
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 7 | $N \le 10$ |
| 2 | 11 | 矩阵中最多有 10 个字符 'C' |
| 3 | 17 | $N, Q \le 500$ |
| 4 | 10 | $N, Q \le 5000$ |
| 5 | 13 | $N \le 100\,000, Q \le 100$ |
| 6 | 15 | 每次交换均满足 $t = 2$ |
| 7 | 27 | 无额外限制 |
样例
样例输入 1
5 2 CPCPC PCCPC 1 1 4 1 1 2
样例输出 1
3 4 5
样例输入 2
5 0 CPPCC PPCCP
样例输出 2
4
样例输入 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
样例输出 3
8 9 10 10 9 8 7 8
说明
第一个样例的说明： 在进行任何交换前，一种最优的交换序列如下： $(1,1) \leftrightarrow (2,1), (1,3) \leftrightarrow (1,4), (1,4) \leftrightarrow (2,4)$。