题目背景

建议先看 D 题题目背景。

题目描述

给定一个长度为 $n$ 的只包含 $\texttt{A,B,C}$ 的字符串 $S$，你可以进行若干次操作，每次操作为：

• 先选择一个区间 $[l,r]$，你需要保证 $1\le l\le r\le n$。

• 再选择三个字符 $pA,pB,pC\in\{\texttt{A,B,C}\}$，并将 $S_{l\dots r}$ 中所有 $\texttt{A}$ 变为 $pA$，所有 $\texttt{B}$ 变为 $pB$，所有 $\texttt{C}$ 变为 $pC$，$pA,pB,pC$ 可以相等。

求出最少需要进行多少次操作才能使得 $S$ 中任意相邻两个字符不同，并输出构造方案。

输入格式

第一行，一个整数 $n$。

第二行，一个长度为 $n$ 的字符串 $S$。

输出格式

第一行，一个整数 $m$，表示你所构造的方案的操作次数。

接下来 $m$ 行，每行两个整数 $l,r$ 和三个字符 $pA,pB,pC$。

你需要保证 $1\le l\le r\le n,pA,pB,pC\in\{\texttt{A,B,C}\}$。

注意：$pA,pB,pC$ 之间不需要，也不应该加空格（参考样例输出）。

5
ABBAA

1
3 4 BAC

5
ABCBA

0

提示

对于 $100\%$ 的数据，$1\le n\le 5\times 10^3,S_i\in\{\texttt{A,B,C}\}$。

	分值	$n$	特殊性质
$\operatorname{Subtask}1$	$1$	无特殊限制	$\forall i\in[1,n),S_i\neq S_{i+1}$
$\operatorname{Subtask}2$	$19$	$\le 10$	无
$\operatorname{Subtask}3$	$10$	无特殊限制	$S_i=\texttt{A}$
$\operatorname{Subtask}4$	$20$		$S_i\in\{\texttt{A,B}\}$
$\operatorname{Subtask}5$		$\le 100$	无
$\operatorname{Subtask}6$	$30$	无特殊限制

评分方法

以下情况将会使你在该测试点获得 $0$ 分：

• 输出格式不满足要求。

• 输出多余信息（包括空格和换行符）

• 构造的方案操作次数与标准答案不同。

• 构造的方案不符合题目要求。

• 时间超限。

如果没有上述情况，你在该测试点获得满分。

保证 SPJ 占用不超过 $100\operatorname{ms},10\operatorname{MB}$。

样例解释 1

一种操作过程如下：

ABBAA

ABABA

可以证明没有更优的方案。

样例解释 2

初始序列已经符合题目要求，直接输出一行 $0$ 即可。