(Unkind) Sandwich Degree

2 secs 1024 MB
Nachia's icon Nachia

問題文

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

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

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

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

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

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

入力

11 行目に 22 つの整数 N,QN,Q (1N3×106,1Q2×105)(1\le N\le 3\times 10^6,1\le Q\le 2\times 10^5) が空白区切りで与えられます。
22 行目に文字列 SS が与えられます。 SS は英小文字からなる長さ NN の文字列です。
33 行目から Q+2Q+2 行目までの各行に、 22 つの整数 a,ba,b (1abN)(1 \leq a \leq b \leq N) が空白区切りで与えられます。

出力

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

入力例1

10 1
experience
1 10

出力例1

36

提出


Go (1.21)