Cs do not change, so let us focus on a maximal segment consisting of As and Bs.

If we assign a weight of \(2\) to A and a weight of \(1\) to B, the operations do not change the total weight. Now, let \(W\) be the total weight of a maximal segment consisting of As and Bs.

Then, the optimal move is as follows.

• If \(W\) is even: change it to \(W/2\) repetitions of A.
• If \(W\) is odd: change it to \((W+1)/2\) repetitions of A followed by one B.

It can be easily seen that this is the lexicographically smallest possible under the fixed total weight. Additionally, this is actually achievable (by temporarily changing all As to Bs and then changing them to As from left to right).

This solution works in \(O(N)\) time.

Sample submission (c++)