Radewoosh received a new puzzle from his parents. This time it contains two cyclic sequences of balls. Each sequence contains $$$n$$$ balls, each of which is either white or black. In total, both sequences contain exactly $$$n$$$ white balls and $$$n$$$ black balls. To describe the puzzle, we will use strings $$$a$$$ and $$$b$$$ - the consecutive characters of string $$$a$$$ denote the colors of the consecutive balls in the first sequence, and the consecutive characters of string $$$b$$$ denote the colors of the consecutive balls in the second sequence. The positions in both sequences are numbered from $$$1$$$ to $$$n$$$.
The puzzle also involves an important number $$$k$$$. In one move, Radewoosh can select a cyclic interval of exactly $$$k$$$ balls from the first sequence and a cyclic interval of exactly $$$k$$$ balls from the second sequence, and swap them. The goal is to make both sequences monochromatic, meaning all the balls in the first sequence are of the same color (all black or all white) and all the balls in the second sequence are of the same color.
Help Radewoosh solve his puzzle in at most $$$n$$$ moves. It can be proven that this is always possible.
The first line of the standard input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 300\,000; 1 \leq k \leq n-1$$$), as described in the task.
The next line contains a string $$$a$$$, consisting of exactly $$$n$$$ characters. If the $$$i$$$-th character is 'B', then the $$$i$$$-th ball in the first sequence is white (as Polish for "white" is "biały"). Otherwise, if the character is 'C', the ball is black (as Polish for "black" is "czarny").
The following line contains a string $$$b$$$, consisting of exactly $$$n$$$ characters, which similarly describes the second sequence of balls.
In total, the strings $$$a$$$ and $$$b$$$ contain exactly $$$n$$$ 'B' characters and $$$n$$$ 'C' characters.
The first line of the output should contain a single number $$$r$$$ ($$$0 \leq r \leq n$$$), indicating the number of moves you want to make.
Next, the output should contain $$$r$$$ lines. Each of them should contain two integers. The numbers in the $$$i$$$-th of these lines, $$$c_i$$$ and $$$d_i$$$ ($$$1 \leq c_i, d_i \leq n$$$), should indicate that you are selecting a cyclic interval from the first sequence starting at position $$$c_i$$$ and a cyclic interval from the second sequence starting at position $$$d_i$$$.
If $$$c_i + k - 1 \leq n$$$, then you are indicating positions $$$c_i, c_i+1, \ldots, c_i + k - 2, c_i + k - 1$$$ in the first sequence. If $$$c_i + k - 1 \geq n + 1$$$, then you are indicating positions $$$c_i, c_i+1, \ldots, n-1, n, 1, 2, \ldots, c_i + k - 2 - n, c_i + k - 1 - n$$$. The value of $$$d_i$$$ has a similar meaning.
After performing all the moves described by you, all the balls in the first sequence should have the same color, and all the balls in the second sequence should have the same color. Note that you do not have to minimize the number of moves - it is enough to make at most $$$n$$$ moves.
6 3 BCCBCC BBCBBC
2 1 3 5 1
The sequences of balls initially look as follows (the first sequence is drawn above, and the second below):
The first move selects these two intervals:
Then swaps them:
The second move selects these two intervals:
Then swaps them:
Note that it would also be correct to move all the black balls to the first sequence and all the white balls to the second sequence.
