Minimize Operations to Achieve Adjacent Distinct Characters

You are given a string \(S\) of length \(n\) containing only the characters A, B and C. You can perform the following operation arbitrarily many times:

• Choose an interval \([l, r]\) with \(1 \le l \le r \le n\).
• Choose three characters \(p_A, p_B, p_C \in \{A,B,C\}\) (they can be equal).
• For every character in the substring \(S[l\dots r]\), replace every occurrence of A by \(p_A\), every occurrence of B by \(p_B\) and every occurrence of C by \(p_C\).

Your goal is to make the final string \(T\) satisfy that every two adjacent characters are different, i.e. for every \(1 \le i < n\), \(T_i \neq T_{i+1}\). Additionally, you must output a construction scheme that attains this goal using the minimum number of operations.

Note: In any single operation, the mapping is applied uniformly to every occurrence of a letter in the chosen interval. That is, if two positions in the interval originally contain the same letter then they will be mapped to the same new letter in that operation. Thus if two adjacent positions in \(S\) are identical, they cannot be fixed in one single operation that covers them both. However, you can fix them in different (possibly single‐element) operations. It can be shown that the minimum number of operations required is equal to the minimum number of indices you need to change (via valid operations) so that the final string has no two consecutive identical characters.

The output format is as follows:

1. Print the minimum number of operations \(k\).
2. Then print \(k\) lines, each describing one operation in the format: l r p_A p_B p_C. Here l and r denote the starting and ending indices (1-indexed) of the interval you operate on. The values p_A, p_B and p_C denote the mapping for characters A, B and C respectively. The mapping must satisfy that for any index where the letter is changed in that operation, its original letter is mapped to a new letter (which may be chosen arbitrarily from \(\{A,B,C\}\) as long as the final adjacent characters in \(T\) are different). For letters that are not the target of change in that interval, you may simply use the identity mapping.
3. Finally, print the final string \(T\) after performing the operations sequentially.

You may assume that an optimal solution always exists. In case there are multiple valid answers, any one is acceptable.

inputFormat

The first line contains a positive integer \(n\) (the length of the string \(S\)).

The second line contains the string \(S\) of length \(n\) consisting only of characters A, B and C.

outputFormat

On the first line, output the minimum number of operations \(k\) required.

Then output \(k\) lines, each containing an operation in the format: l r p_A p_B p_C.

Finally, output the final string \(T\) (of length \(n\)) that has no two consecutive identical characters.

sample

3
ABA

0
ABA