P7919 [Kubic] ABC

It is recommended to read the background of Problem D first.

You are given a string $S$ of length $n$ that contains only $\texttt{A,B,C}$. You may perform several operations. In each operation: - First choose an interval $[l,r]$, and you must ensure that $1\le l\le r\le n$. - Then choose three characters $pA,pB,pC\in\{\texttt{A,B,C}\}$, and change all $\texttt{A}$ in $S_{l\dots r}$ into $pA$, all $\texttt{B}$ into $pB$, and all $\texttt{C}$ into $pC$. **$pA,pB,pC$ may be equal**. Find the **minimum** number of operations needed to make **any two adjacent characters in $S$ different**, and **output a construction**.

The first line contains an integer $n$. The second line contains a string $S$ of length $n$.

The first line contains an integer $m$, the number of operations in your constructed plan. The next $m$ lines each contain two integers $l,r$ and three characters $pA,pB,pC$. You must ensure that $1\le l\le r\le n,pA,pB,pC\in\{\texttt{A,B,C}\}$. **Note: There is no need to, and you should not, add spaces between $pA,pB,pC$ (see the sample output).**

For $100\%$ of the testdata, $1\le n\le 5\times 10^3,S_i\in\{\texttt{A,B,C}\}$. ## Constraints ||Score|$n$|Special Property| |:-:|:-:|:-:|:-:| |$\operatorname{Subtask}1$|$1$|No special limits|$\forall i\in[1,n),S_i\neq S_{i+1}$| |$\operatorname{Subtask}2$|$19$|$\le 10$|None| |$\operatorname{Subtask}3$|$10$|No special limits|$S_i=\texttt{A}$| |$\operatorname{Subtask}4$|$20$|No special limits|$S_i\in\{\texttt{A,B}\}$| |$\operatorname{Subtask}5$|$20$|$\le 100$|None| |$\operatorname{Subtask}6$|$30$|No special limits|None| ### Scoring You will get $0$ points on this test point if any of the following happens: - The output format does not meet the requirements. - You output extra information (including spaces and newline characters). - The number of operations in your constructed plan is different from the official answer. - Your constructed plan does not satisfy the problem requirements. - Time limit exceeded. If none of the above happens, you will get full points on this test point. **It is guaranteed that the SPJ uses no more than $100\operatorname{ms},10\operatorname{MB}$.** ### Sample Explanation 1 One possible sequence of operations is: `ABBAA` `ABABA` It can be proven that there is no better plan. ### Sample Explanation 2 The initial sequence already satisfies the requirements, so you can directly output a single line $0$. Translated by ChatGPT 5