AT_scpc2026_div2_d Coloring

#### 表示言語 / / Lulu and Terra are playing with red, green, and blue paints. Lulu and Terra want to paint a picture consisting of $ N $ square cells arranged in a row. Terra first painted part of the picture and then handed the rest over to Lulu. The picture painted by Terra can be represented by a string $ S $ of length $ N $ consisting of `R`, `G`, `B`, and `X`. If the $ i $ -th character of $ S $ is `R`, the $ i $ -th cell is painted red; if it is `G`, it is painted green; if it is `B`, it is painted blue; and if it is `X`, it is an unpainted empty cell. Lulu does not like the picture Terra painted, so Lulu decided to cut out a certain interval of the picture and make that interval into a **perfect picture**. According to Lulu, a **perfect picture** is a picture satisfying the following two conditions. 1. Every cell must be painted one of red, green, and blue. 2. Lulu likes colorful things, so any two adjacent cells must always have different colors. Lulu can paint empty cells that Terra did not paint in any desired color, and can also repaint cells Terra has already painted in a different color. The interval Lulu cuts out is represented by two integers $ l $ and $ r $ , meaning the consecutive interval from the $ l $ -th cell to the $ r $ -th cell from the left. For each of the $ Q $ ways to cut out a certain interval, tell Lulu the minimum number of cells that must be repainted to make the interval a **perfect picture**.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ S $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_Q $ $ r_Q $

Print $ Q $ lines. For each case, print one line containing the minimum number of cells Lulu must repaint to complete the **perfect picture**.

### Constraints - $ 1 \leq N, Q \leq 300\,000 $ - The string $ S $ consists only of uppercase letters `R`, `G`, `B`, and `X`. - For each query, $ 1 \leq l_i \leq r_i \leq N $ . - All given numbers are integers.