We have to color every cell in the given interval with one of the three colors.

A cell marked X is still empty, so we may color it with any color without paying any cost. A cell that is already colored may also be repainted into another color, but this costs \(1\).

The goal is to make every pair of adjacent cells have different colors.

If two adjacent cells already have different colors, they do not cause any problem. Also, since there are three available colors, cells marked X can always be colored appropriately.

Therefore, the only problematic parts are maximal contiguous segments of the same already-colored character, such as

\[ \underbrace{\mathtt{RR\cdots R}}_{k}. \]

For a segment of length \(k\) consisting of the same color, we need to repaint at least one cell from each adjacent equal pair. This requires at least

\[ \left\lfloor \frac{k}{2} \right\rfloor \]

repaints.

This lower bound is achievable by repainting every second cell in the segment. Hence, the cost of one same-color segment is

\[ \left\lfloor \frac{\text{length}}{2} \right\rfloor. \]

For a segment consisting of X, the cost is \(0\).

Now split the whole string into maximal blocks of equal characters. For each block, store its start position, end position, character, and cost. Also store, for every position, the index of the block containing it.

Build a prefix sum array of block costs. Then the total cost of blocks completely contained in a query interval can be computed in \(O(1)\) time.

Consider a query interval \([l,r]\). Let \(L\) be the block containing \(l\), and let \(R\) be the block containing \(r\).

If \(L=R\), then the query interval is contained in one block. If this block consists of X, the answer is \(0\). Otherwise, the answer is

\[ \left\lfloor\frac{r-l+1}{2}\right\rfloor. \]

Now suppose \(L<R\).

For the left endpoint block, only the part from \(l\) to the end of the block is included. For the right endpoint block, only the part from the start of the block to \(r\) is included.

If an endpoint block consists of X, its contribution is \(0\). Otherwise, if the included length is \(k\), its contribution is

\[ \left\lfloor\frac{k}{2}\right\rfloor. \]

The blocks strictly between \(L\) and \(R\) are fully contained in the query interval, so their total contribution is obtained from the prefix sum of block costs.

Thus, after preprocessing, each query can be answered in \(O(1)\) time.

The total time complexity is \({\cal O}(N+Q)\).