AT_abc122_c [ABC122C] GeT AC

[problemUrl]: https://atcoder.jp/contests/abc122/tasks/abc122_c `A`, `C`, `G`, `T` からなる長さ $ N $ の文字列 $ S $ が与えられます。以下の $ Q $ 個の問いに答えてください。 - 問 $ i $ ($ 1\ \leq\ i\ \leq\ Q $): 整数 $ l_i,\ r_i $ ($ 1\ \leq\ l_i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ S $ $ l_1 $ $ r_1 $ $ : $ $ l_Q $ $ r_Q $

$ Q $ 行出力せよ。$ i $ 行目に問 $ i $ への答えを出力すること。

### 注記 文字列 $ T $ の部分文字列とは、$ T $ の先頭と末尾から $ 0 $ 文字以上を取り去って得られる文字列です。 例えば、`ATCODER` の部分文字列には `TCO`, `AT`, `CODER`, `ATCODER`, `` (空文字列) が含まれ、`AC` は含まれません。 ### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ S $ は長さ $ N $ の文字列である。 - $ S $ の各文字は `A`, `C`, `G`, `T` のいずれかである。 - $ 1\ \leq\ l_i\