(Unkind) Sandwich Degree

問題文

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

$S[i]$ で文字列 $S$ の前から $i$ 番目の文字を表します。

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

$1 \leq i \lt j \leq |S|$ を満たす整数の組 $(i,j)$ すべてについて以下で求めた $h$ を足し合わせた値が 嬉しさ である。

• $S[i]$ と $S[j]$ が同じ文字なら $h = j-i+1$
• $S[i]$ と $S[j]$ が異なる文字なら $h = 0$

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

入力

$1$ 行目に $2$ つの整数 $N,Q$ $(1\le N\le 3\times 10^6,1\le Q\le 2\times 10^5)$ が空白区切りで与えられます。
$2$ 行目に文字列 $S$ が与えられます。 $S$ は英小文字からなる長さ $N$ の文字列です。
$3$ 行目から $Q+2$ 行目までの各行に、 $2$ つの整数 $a,b$ $(1 \leq a \leq b \leq N)$ が空白区切りで与えられます。

出力

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

入力例1

10 1
experience
1 10

出力例1

36