题目描述

有一个 $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$。