题目描述

译自 CCO 2022 Day2 T3「Good Game」。

Finn 正在玩一个叫做 Twos and Threes 的游戏。Twos and Threes 是一个在一维棋盘上的单人游戏。一开始，有 $N$ 个方块排成一行，每个方块有一个标签 $\texttt{A}$ 或 $\texttt{B}$，从左到右编号依次为 $1$ 到 $N$。

Finn 可以进行以下操作： 选择 $2$ 或 $3$ 个连续的标签相同的方块，将它们从棋盘上移除，再将剩余的方块从左到右连接起来并重新编号方块。

如果棋盘上的所有方块都被移除，Finn 就赢得了游戏。你的任务是帮助 Finn 确定一个赢得游戏的操作序列，或者告诉他游戏无法获胜。

输入格式

第一行包含一个整数 $N$。

第二行包含一个长度为 $N$ 的字符串 $S$，表示游戏开始时的标签。$S$ 中的每个字符都是 $\texttt{A}$ 或 $\texttt{B}$。

输出格式

如果存在赢得游戏的操作序列，第一行输出一个整数 $K$，表示操作次数。在接下来的 $K$ 行中，输出两个空格分隔的整数 $i,j$，表示移除位于 $[i,i+j-1]$ 的方块的一次操作（$j$ 只能是 $2$ 或 $3$）。否则输出 $-1$。

如果有多个赢得游戏的操作序列，你可以输出任何一个。

样例

输入

9
ABAABBBAA

输出

4
6 2
3 2
2 2
1 3

样例解释

操作过程如下（下划线表示每次移除的方块）：

1. 初始状态：$\texttt{ABAAB}\underline{\texttt{BB}}\texttt{AA}$（移除第 $6 \sim 7$ 位，$j=2$）→ 剩余 $\texttt{ABAA BAA}$（连接后为 $\texttt{AB AABAA}$）；
2. 当前状态：$\texttt{AB}\underline{\texttt{AA}}\texttt{BAA}$（移除第 $3 \sim 4$ 位，$j=2$）→ 剩余 $\texttt{AB BAA}$（连接后为 $\texttt{AB BAA}$）；
3. 当前状态：$\texttt{A}\underline{\texttt{BB}}\texttt{AA}$（移除第 $2 \sim 4$ 位？实际按输出操作：移除第 $2 \sim 3$ 位，$j=2$，此处需结合重新编号规则，最终剩余 $\texttt{AAA}$）；
4. 最终状态：$\underline{\texttt{AAA}}$（移除第 $1 \sim 3$ 位，$j=3$）→ 棋盘清空，游戏获胜。

数据范围与提示

对于所有的数据，有 $1 \leq N \leq 10^6$。

详细子任务附加限制及分值如下表所示：