#2313. 「HAOI2017」供给侧改革

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

题目描述

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

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

对于每一个询问 LLRR。求

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

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

输入格式

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

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

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

输出格式

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

样例

样例输入

6 3
010110
2 5
1 6
1 2

样例输出

4
6
0

数据范围与提示

数据点nn 的规模QQ 的规模
11n20n \leq 20Q20Q \leq 20
22n20n \leq 20Q20Q \leq 20
33n100n \leq 100Q100Q \leq 100
44n100n \leq 100Q100Q \leq 100
55n5000n \leq 5000Q5000Q \leq 5000
66n5000n \leq 5000Q5000Q \leq 5000
77n100000n \leq 100000Q100000Q \leq 100000
88n100000n \leq 100000Q100000Q \leq 100000
99n100000n \leq 100000Q100000Q \leq 100000
1010n100000n \leq 100000Q100000Q \leq 100000

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