题目背景

为了打败大魔王$shuji$ ，$KKY$ 苦学终极魔法，但总是因为浪费太多时间导致未能阻止 $shuji$毁灭世界。幸好异世界女神可以借助魔力给 $KKY$ 帮助他回到过去。但是 $KKY$ 一直潜心专研终极魔法，没用多余时间去学习新的TLE 魔法回到过去。于是 $KKY$ 找到了天赋异禀的你，请你告诉 $KKY$ 如何才能开启时间漩涡回到过去，重新挑战大魔王 $shuji$ $！$

题目描述

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

翻转第 $l$ 个字符到 $r$ 个字符对应的区间，该字符串有多少"$kky$"子序列。 子序列指按原串顺序取若干字母（可以不连续）形成的新字符串。如" $kkykyy$ "存在$7$个" $kky$ "子序列。

数据描述

输入

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

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

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

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

$1 \leq q \leq 5 \times 10^3$

$1 \leq l , r \leq n$

$0 \le r-l \le 1000$

输出

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

样例

6 2 
kkykyy
1 3
3 4

6
9

Limitation

1s, 1024KiB for each test case.