Problem Description

Finn is playing a game called Twos and Threes. Twos and Threes is a single-player game played on a one-dimensional board. In the initial position, there are $N$ tiles in a row, and each tile is labeled $\tt{A}$ or $\tt{B}$. The tiles are numbered from left to right from $1$ to $N$. Finn can perform the following move:

• Choose $2$ or $3$ consecutive tiles that have the same label, remove them from the board, and then connect the remaining tiles and renumber them from left to right.

If all tiles on the board are removed, Finn wins the game. Your task is to help Finn find a sequence of moves that wins the game, or determine that the game cannot be won.

Input Format

The first line contains an integer $N$.

The second line contains a string $S$, representing the labels at the start of the game. $S$ has $N$ characters, and each character of $S$ is either $\tt{A}$ or $\tt{B}$.

Output Format

If there exists a winning sequence of moves, output $K$ on the first line, the number of moves in the sequence. In the next $K$ lines, output two integers $i, j$ separated by a space, indicating a move that removes the tiles in $[i, i + j - 1]$.

If there is no winning sequence of moves, output $-1$.

If there are multiple winning sequences of moves, you may output any one of them.

9
ABAABBBAA

4
6 2
3 2
2 2
1 3

Hint

Sample Explanation

The moves are as follows:

$$\begin{aligned} &\tt{ABAAB\underline{BB}AA}\\ &\tt{AB\underline{AA}BAA}\\ &\tt{A\underline{BB}AA}\\ &\tt{\underline{AAA}}\\ \end{aligned}$$

Constraints

For all testdata, $1 \leq N \leq 10^{6}$.

Subtask ID	Points	Range of $N$
$1$	$12$	$1 \leq N \leq 15$
$2$	$24$	$1 \leq N \leq 300$
$3$	$28$	$1 \leq N \leq 6000$
$4$	$36$	$1 \leq N \leq 10^6$

Hint

Translated by ChatGPT 5