故事的终章

kky发现上场没人补题？于是....

题目背景

$KKY$ 在女神的协助下，终于学会了 终极魔法 打败了大魔王$shuji$，可是他没想到女神想要打败$shuji$是为了更好的统治这个世界！据说上一代勇者$ckl$凭借自己的天赋学会了 术式逆解！ ，可以破解一切魔法，但是女神为了稳固自己的地位夺走了$ckl$的生命，导致他没办法帮助 $KKY$ 拯救世界。

突然，机智的 $KKY$ 灵光一闪，既然魔法可以回到过去，那么是不是可以回到过去复活$ckl！？$但是女神为了防止 $KKY$ 像魔王 $shuji$ 和上代用勇者 $ckl$ 那样强大，都是把自己的魔力借给 $KKY$ ，导致 $KKY$ 的魔力如此稀薄，以至于只能发动两次魔法……

$KKY$毫不犹豫的就发动了他无比熟练的回到过去 魔法，但是没想到因为自己的魔力过于稀薄居然失败了$！！！$仅仅只剩最后一次的机会，$KKY$无比沮丧，想起自己前世也是如此不堪，看到难题 $Wrong Answer$ 之后连再写一次的勇气都没有。

$KKY$ 非常不甘！他也想当一次$“hero”$$！$于是他想$WA$之后再试一次！！！但是为了提高成功率，他找到了大隐于世的你，请求你能够帮助他完成魔法的解析，让$KKY$发动的准确率更高！

题目描述

穿越时间的魔法是一段 咒语 ，你需要找到要回到过去的时间段 [ l , r ] ,然后将区间中的咒语反转后找到最初$ckl$存在的时间节点$！$（反转后不改变原字符串）

翻转第 $l$ 个字符到 $r$ 个字符对应的区间，该字符串有多少"$ckl$"子序列。

子序列指按原串顺序取若干字母（可以不连续）形成的新字符串。如" $cckkll$ "存在$8$个" $ckl$ "子序列。

数据描述

输入

第一行，两个整数 $n，q$ ；表示咒语长度和询问次数。

第二行，一行长度为 $n$ 且只包含小写字母的字符串。

接下来q行输入两个整数 $l，r$ 表示反转区间。

$1 \leq n , q \leq 1\times10^5$

$1 \leq l , r \leq n$

输出

输出$q$行，每行一个整数代表询问的答案。

样例

6 2
cckkll
1 2
1 6

8 
0

Limitation

1s, 1024KiB for each test case.