AT_scpc2026_div2_d Coloring

#### 表示言語 / / ルルとテラは赤色，緑色，青色の絵の具で塗り絵をしている． ルルとテラは $ N $ 個の正方形のマスが一列につながった絵を塗ろうとしている．テラが先に絵の一部を塗った後，残りの部分をルルに渡した．テラが塗った絵は `R`, `G`, `B`, `X` からなる長さ $ N $ の文字列 $ S $ で表される．文字列 $ S $ の $ i $ 番目の文字が `R` なら赤色，`G` なら緑色，`B` なら青色，`X` なら塗られていない空のマスを表す． ルルはテラが塗った絵が気に入らず，絵の特定の区間を切り出して，その区間を **完璧な絵** にすることにした．ルルが考える **完璧な絵** とは，次の $ 2 $ つの条件を満たす絵である． 1. すべてのマスは赤色，緑色，青色のいずれかで塗られていなければならない． 2. ルルは色とりどりなものが好きなので，隣り合う $ 2 $ つのマスの色は常に異ならなければならない． ルルは，テラが塗っていない空のマスを好きな色で塗ることができ，テラがすでに塗ったマスの色を別の色に塗り直すこともできる． ルルが切り出す区間は $ 2 $ つの整数 $ l $ と $ r $ で表され，これは左から $ l $ 番目のマスから $ r $ 番目のマスまでの連続した区間を意味する．特定の区間を切り出す $ Q $ 通りの場合について，ルルが **完璧な絵** を作るために塗り直す必要があるマスの最小個数を求めよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ S $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_Q $ $ r_Q $

$ Q $ 行にわたり，各場合について，ルルが **完璧な絵** を完成させるために塗り直す必要があるマスの最小個数を $ 1 $ 行に出力せよ．

### Constraints - $ 1 \leq N, Q \leq 300\,000 $ - 文字列 $ S $ は英大文字 `R`, `G`, `B`, `X` のみからなる． - 各クエリについて， $ 1 \leq l_i \leq r_i \leq N $ - 入力される数値はすべて整数である．