(Unkind) Sandwich Degree

2 secs 1024 MB
Nachia

問題文


(21:55更新) の条件が誤りでした。

で文字列 の前から 番目の文字を表します。

Nachia 君が好きな文字列の一つに、 experience があります。なぜなら、同じ文字が離れて存在したり、たくさん出現したりしているからです。ここで、 Nachia 君は文字列に対して 嬉しさ を定義しました。文字列 嬉しさ は以下のように求めます。

を満たす整数の組 すべてについて以下で求めた を足し合わせた値が 嬉しさ である。

  • が同じ文字なら
  • が異なる文字なら

長さ の文字列 が与えられます。同時に 個の組 が与えられます。各組 について、 番目から 番目まで (両端を含む) の文字を取り出した部分文字列 嬉しさ を求めてください。

入力


行目に つの整数 が空白区切りで与えられます。
行目に文字列 が与えられます。 は英小文字からなる長さ の文字列です。
行目から 行目までの各行に、 つの整数 が空白区切りで与えられます。

出力


の組それぞれについて、求める 嬉しさ を整数で出力し、改行してください。

入力例1


10 1
experience
1 10

出力例1


36

提出


Go (1.14)