C0948 [HAOI2017]供给侧改革

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$ 之间随机产生的。

样例输入 1

6 3
010110
2 5
1 6
1 2

样例输出 1

4
6
0