Background

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

Problem Description

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.

Input Format

The first line contains an integer $n$.

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

Output Format

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).

5
ABBAA

1
3 4 BAC

5
ABCBA

0

Hint

For $100\%$ of the testdata, $1\le n\le 5\times 10^3,S_i\in\{\texttt{A,B,C}\}$.

Constraints

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