[Kubic] ABC

建议先看 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$|$20$|$\le 100$|无| |$\operatorname{Subtask}6$|$30$|无特殊限制|无| ### 评分方法 以下情况将会使你在该测试点获得 $0$ 分： - 输出格式不满足要求。 - 输出多余信息（包括空格和换行符） - 构造的方案操作次数与标准答案不同。 - 构造的方案不符合题目要求。 - 时间超限。 如果没有上述情况，你在该测试点获得满分。 **保证 SPJ 占用不超过 $100\operatorname{ms},10\operatorname{MB}$**。 ### 样例解释 1 一种操作过程如下： `ABBAA` `ABABA` 可以证明没有更优的方案。 ### 样例解释 2 初始序列已经符合题目要求，直接输出一行 $0$ 即可。