4325: 「HAOI2017」供给侧改革
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Anihc 国提高社会生产力水平，落实好以人民为中心的发展思想。决定进行供给侧结构性改革。
为了提高供给品质，你调查了某个产业近来 $ n $ 个时期的供求关系平衡情况，每个时期的情况都用 $ 0 $ 或 $ 1 $ 中的一个数字来表示，于是这就是—个长度为 $ n $ 的 $ 01 $ 字符串 $S$ 。为了更好的了解这一些数据，你需要解决一些询问，我们令 $ \operatorname{data}(l,r) $ 表示：在字符串 $S$ 中，起始位置在$ [l,r] $之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。
对于每一个询问 $ L , R $。求
$$ \mathit{ans} = \sum\limits_{ L \le i \lt R } \operatorname{data}(i, R) $$
由于你其实根本没有时间调查，所以这些数据都是乱编的，即串 $ S $ 中的每一位都是在 $ 0 $ 和 $ 1 $ 之间随机产生的。
输入
第一行 $ 2 $ 个整数 $ n $，$ Q $，表示字符串的长度，以及询问个数。
接下来一行长度为 $n$ 的一个 $01$ 串 $S$。
接下来 $Q$ 行，每行 $2$ 个整数 $L,R$，一个询问 $L.R$ 。
输出
共 $Q$ 行，每行一个整数，表示对应询问的答案。
样例输入 复制
6 3
010110
2 5
1 6
1 2样例输出 复制
4
6
0提示
数据范围：|数据点|$ n $ 的规模|$ Q $ 的规模| |:-:|:-:|:-:| |$ 1 $| $ n \leq 20$|$Q \leq 20 $| |$ 2 $|$ n \leq 20$|$ Q \leq 20 $| |$ 3 $|$ n \leq 100$|$Q \leq 100 $| |$ 4 $ |$ n \leq 100$|$ Q \leq 100 $| |$ 5 $| $ n \leq 5000$|$Q \leq 5000 $| |$ 6 $| $ n \leq 5000$|$ Q \leq 5000 $| |$ 7 $| $ n \leq 100000$|$ Q \leq 100000 $| |$ 8 $| $ n \leq 100000$|$Q \leq 100000 $| |$ 9 $|$ n \leq 100000$| $Q \leq 100000 $| |$ 10 $ |$ n \leq 100000$|$ Q \leq 100000 $| 对于所有的数据保证：$ n \leq 100000 $，$ Q\leq 100000 $，$ 1\leq L