There is a $2 \times n$ (2 rows, $n$ columns) chessboard, where each cell contains either a chocolate bean or a pea.

For an initial configuration, you can perform a number of swaps, where each swap is defined as:

• Choose two cells that share a common edge and swap the beans in those two cells.

You need to reach a final configuration where all peas are located in the top-left of the board. Specifically:

• For both the first and second rows: within each row, all peas must be to the left of all chocolate beans (i.e., they form a prefix).
• Let $x$ be the number of peas in the first row and $y$ be the number of peas in the second row. Then $x \ge y$.

Let C represent a chocolate bean and P represent a pea. The following is an example of a possible final configuration:

PPPPC
PCCCC

You want to perform a sequence of swaps to move all peas to the top-left of the board.

There are $q$ queries. Each query involves swapping the beans in two adjacent cells of the initial state.

You need to calculate the minimum number of swaps required to reach the final configuration for the initial state before any queries, and after each of the $q$ queries, for a total of $q+1$ states.

Input

The first line contains two integers $n$ and $q$.

The next two lines each contain a string of length $n$, representing the initial state of the board. C represents a chocolate bean and P represents a pea.

The next $q$ lines each contain three integers $op, x, y$.

• $op=1$: Swap the beans at $(x, y)$ and $(x, y+1)$.
• $op=2$: Swap the beans at $(x, y)$ and $(x+1, y)$.
• It is guaranteed that the two cells involved in the operation exist on the board.

Output

Output $q+1$ lines, each representing the answer for the corresponding state.

Examples

Input 1

5 2
CPCPC
PCCPC
1 1 4
1 1 2

Output 1

3
4
5

Note 1

For the first initial state, swap (1,1)-(2,1), (1,3)-(1,4), and (1,4)-(2,4).

Input/Output 2~8

See the provided files. They satisfy the properties of Subtasks 1~7 respectively.

Constraints

For all data, $1 \le n \le 10^6, 0 \le q \le 10^6$.