[八省联考2018]制胡窜

题目描述

对于一个字符串 $s$,我们定义 $|s|$ 表示 $s$ 的长度。 接着,我们定义 $s_i$ 表示 $s$ 中第 $i$ 个字符,$s_{l,r}$ 表示由 $s$ 中从左往右数,第 $l$ 个字符到第 $r$ 个字符依次连接形成的字符串。特别的,如果 $l \gt r$,或者 $l \notin [1, |s|]$,或者 $r \notin [1, |s|]$,我们可以认为 $s_{l,r}$ 为空串。 给定一个长度为 $n$ 的仅由数字构成的字符串 $s$,现在有 $q$ 次询问,第 $k$ 次询问会给出 $s$ 的一个子串 $s_{l,r}$,请你求出有多少对 $(i, j)$,满足 $1 \leq i \lt j \leq n$,$i + 1 < j$,且 $s_{l,r}$ 出现在 $s_{1,i}$ 中或 $s_{i+1,j-1}$中或 $s_{j,n}$ 中。

输入输出格式

输入格式


输入的第一行是两个整数,分别表示字符串长度 $n$ 和询问次数 $q$。 第二行有一个长度为 $n$ 的只包含数字字符的字符串,表示 $s$。 接下来 $q$ 行,每行两个正整数 $l$ 和 $r$,表示此次询问的子串是 $s_{l,r}$。

输出格式


对于每个询问,输出一行一个整数表示答案。

输入输出样例

输入样例 #1

5 2
00100
1 2
1 3

输出样例 #1

5
1

说明

| 测试点 | $n$ | $q$ | 其它约定 | | :----------: | :-------: | :-------: | :-----------------------------------: | | $1$ | $=50$ | $=100$ | 无 | | $2 \sim 3$ | $=300$ | $=300$ | 无 | | $4 \sim 5$ | $=2000$ | $=3000$ | 无 | | $6 \sim 9$ | $=100000$ | $=100000$ | $\sum \lvert s_{l,r} \rvert \le 10^6$ | | $10 \sim 12$ | $=30000$ | $=50000$ | 无 | | $13$ | $=100000$ | $=100000$ | $s$ 中只有 $0$ | | $14 \sim 20$ | $=100000$ | $=300000$ | 无 | 对于所有测试数据,$1 \le n \le 10^5$,$1 \le q \le 3 \times 10^5$,$1 \le l \le r \le n$,$s$ 中只有数字字符。