Description
你调查了某个产业近来 n 个时期的供求关系平衡情况，每个时期的情况都用 0 或 1 中的一个数字来表示。于是这就是—个长度为 n 的 01 字符串 S。为了更好的了解这一些数据，你需要解决一些询问，我们令 data(L,R) 表示：在字符串 S 中，起始位置在 [L,R] 之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。
对于每一个询问 L,R，求：
ans=∑L⩽i<R data(i,R)
数据范围保证，串 S 中的每一位都是在 0 和 1 之间随机产生的。
Input
第一行 2 个整数 n,Q，表示字符串的长度，以及询问个数。
接下来一行长度为 n 的一个 01 串 S。
接下来 Q 行，每行 2 个整数 L,R，一个询问 L,R。
Output
共 Q 行，每行一个整数，表示对应询问的答案。
HINT
数据规模与约定
|
数据点
|
n 的规模
|
Q 的规模
|
|
1,2
|
⩽20
|
⩽20
|
|
3,4
|
⩽100
|
⩽100
|
|
5,6
|
⩽5×103
|
⩽5×103
|
|
7,8,9,10
|
⩽105
|
⩽105
|
对于所有的数据保证：n⩽10
5，Q⩽10
5，1⩽L<R⩽n，01串随机生成。