Matrix Ball Rearrangement

You are given a 2×N matrix. Each cell contains a ball which is either red or blue. The goal is to rearrange the balls by swapping adjacent balls (two balls are adjacent if and only if their cells share a common edge) so that all blue balls lie in the top‐left region and all red balls lie in the bottom‐right region. More formally, after the rearrangement there should be no pair consisting of a red ball and a blue ball such that the red ball is located above or to the left of the blue ball.

It can be shown that any valid final configuration satisfying the above condition has the following structure. Let B be the total number of blue balls and let N be the number of columns (each row has N cells). Then:

• If B ≤ N: In the final configuration the first B cells of the first row are blue and the remaining (N − B) cells of the first row along with all cells of the second row are red.
• If B > N: The entire first row must be blue, and in the second row the first (B − N) cells are blue and the remaining (2N − B) cells are red.

You are allowed to swap adjacent balls (where two cells are adjacent if they share a common edge) any number of times in order to achieve one of the valid final configurations. Prove that the minimum number of adjacent swaps required is exactly equal to the number of inversions in the 1D sequence obtained by reading the matrix in row‐major order (first row from left to right followed by the second row from left to right), where we treat red as 1 and blue as 0. That is, if we denote the sequence by A[0...2N − 1] with A[i] = 1 if the corresponding ball is red and 0 if it is blue, then the answer is:

\[ \text{Answer} = \sum_{i=0}^{2N-1} \bigl[ A[i]=1 \bigr] \cdot \Bigl((2N - i - 1) - \sum_{j=i+1}^{2N-1} \bigl[A[j]=1\bigr]\Bigr). \]

In addition, you are given Q queries. In each query, two adjacent cells (given by their row and column indices) are selected and their balls are swapped. After each swap, you must output the new minimum number of swaps required to reach a valid final configuration from the current matrix state.

Note: For a swap between two adjacent cells located at positions with row‐major indices i and j (with i < j), one can prove that the change in the inversion count is:

\[ \Delta = \begin{cases} + (j-i), & \text{if the ball at index } i \text{ is blue and at } j \text{ is red},\\ - (j-i), & \text{if the ball at index } i \text{ is red and at } j \text{ is blue},\\ 0, & \text{if both balls are of the same color.} \end{cases} \]

You need to output the inversion count (i.e. the minimum number of swaps required) for the initial configuration as well as after each query.

inputFormat

The first line contains two integers N and Q — the number of columns and the number of queries, respectively.

The next two lines each contain a string of length N consisting of the characters 'R' and 'B', representing the first and second rows of the matrix respectively.

Then Q lines follow. Each of these lines contains four integers r1 c1 r2 c2 (1-indexed) indicating that the balls in the cell at row r1, column c1 and the cell at row r2, column c2 are swapped. It is guaranteed that the two cells are adjacent (i.e. they share a common edge).

outputFormat

Output Q+1 lines. The first line should contain the minimum number of adjacent swaps required for the initial matrix configuration. Then, after each query, output one line containing the new minimum number of swaps required.

sample

2 1
RB
BR
1 1 2 1

2
0

</p>