Pero has a matrix with two rows and $N$ columns. Each cell of the matrix contains either a red or a blue ball. Pero's goal is to rearrange the balls in the matrix such that all blue balls are located "top-left" and all red balls are "bottom-right". More precisely, after the rearrangement, there must be no red ball located above or to the left of any blue ball.
To achieve his goal, Pero will swap some two adjacent balls a certain number of times. Balls are considered adjacent if their corresponding cells in the matrix share a side. Pero is interested in the minimum number of swaps required to reach the desired arrangement.
Additionally, Pero will swap two adjacent balls in the matrix $Q$ times, and after each change, he is interested in the answer for the current state of the matrix. Help Pero and output the answer for the initial matrix and after each change.
Input
The first line contains the numbers $N$ and $Q$, the number of columns in the matrix and the number of changes Pero made.
The next two lines contain the description of Pero's matrix. Each line consists of $N$ characters 'C' or 'P', representing a red or a blue ball, respectively.
Each of the next $Q$ lines contains three natural numbers $t, x, y$ ($1 \le t \le 2, 1 \le x \le 2, 1 \le y \le N$), which represent the performed swaps in order. If $t = 1$, the adjacent cells $(x, y)$ and $(x, y + 1)$ are swapped, and if $t = 2$, the adjacent cells $(x, y)$ and $(x + 1, y)$ are swapped. It is guaranteed that both of these cells are located within the matrix.
Output
Output $Q + 1$ lines. For $i = 0, 1, \dots, Q$, output the minimum number of swaps required to reach the desired arrangement after $i$ changes.
Subtasks
In all subtasks, $1 \le N \le 10^6$ and $0 \le Q \le 10^6$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 7 | $N \le 10$ |
| 2 | 11 | There are at most 10 'C' letters in the matrix. |
| 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$ holds for every change. |
| 7 | 27 | No additional constraints. |
Examples
Input 1
5 2 CPCPC PCCPC 1 1 4 1 1 2
Output 1
3 4 5
Input 2
5 0 CPPCC PPCCP
Output 2
4
Input 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
Output 3
8 9 10 10 9 8 7 8
Note
Explanation of the first example: One example of an optimal sequence of swaps before the changes is: $(1,1)\leftrightarrow(2,1), (1,3)\leftrightarrow(1,4), (1,4)\leftrightarrow(2,4)$.