题目描述

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

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

对于每一个询问L,R.求

$ans = \sum_{L\le i < R} 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    <= 20    <= 20
2    <= 20    <= 20
3    <= 100    <= 100
4    <= 100    <= 100
5    <= 5000    <= 5000
6    <= 5000    <= 5000
7    <= 100000    <= 100000
8    <= 100000    <= 100000
9    <= 100000    <= 100000
10    <= 100000    <= 100000

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