#2313. 「HAOI2017」供给侧改革

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: __stdcall

题目描述

Anihc 国提高社会生产力水平,落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质,你调查了某个产业近来 n n 个时期的供求关系平衡情况,每个时期的情况都用 0 0 1 1 中的一个数字来表示,于是这就是—个长度为 n n 01 01 字符串 SS 。为了更好的了解这一些数据,你需要解决一些询问,我们令 data(l,r) \operatorname{data}(l,r) 表示:在字符串 SS 中,起始位置在[l,r] [l,r] 之间的这些后缀之中,具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问 L L R R 。求

ans=Li<Rdata(i,R) \mathit{ans} = \sum\limits_{ L \le i \lt R } \operatorname{data}(i, R)

由于你其实根本没有时间调查,所以这些数据都是乱编的,即串 S S 中的每一位都是在 0 0 1 1 之间随机产生的。

输入格式

第一行 2 2 个整数 n n Q Q ,表示字符串的长度,以及询问个数。

接下来一行长度为 nn 的一个 0101SS

接下来 QQ 行,每行 22 个整数 L,RL,R,一个询问 L.RL.R

输出格式

QQ 行,每行一个整数,表示对应询问的答案。

样例

样例输入

6 3
010110
2 5
1 6
1 2

样例输出

4
6
0

数据范围与提示

数据点 n n 的规模 Q Q 的规模
1 1 n20 n \leq 20 Q20Q \leq 20
2 2 n20 n \leq 20 Q20 Q \leq 20
3 3 n100 n \leq 100 Q100Q \leq 100
4 4 n100 n \leq 100 Q100 Q \leq 100
5 5 n5000 n \leq 5000 Q5000Q \leq 5000
6 6 n5000 n \leq 5000 Q5000 Q \leq 5000
7 7 n100000 n \leq 100000 Q100000 Q \leq 100000
8 8 n100000 n \leq 100000 Q100000Q \leq 100000
9 9 n100000 n \leq 100000 Q100000Q \leq 100000
10 10 n100000 n \leq 100000 Q100000 Q \leq 100000

对于所有的数据保证:n<=100000 n <= 100000 Q<=100000 Q<= 100000 1<=L<R<=n 1<=L<R<=n 0101 串随机生成。