题目描述
对于一个字符串 $S$，我们定义 $|S|$ 表示 $S$ 的长度。
接着，我们定义 $Si$ 表示 $S$ 中第 $i$ 个字符，$S{L,R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。特别的，如果 $L > R$ ，或者 $L < [1, |S|]$, 或者 $R < [1, |S|]$ 我们可以认为 $S_{L,R}$ 为空串。
给定一个长度为 $n$ 的仅由数字构成的字符串 $S$，现在有 $q$ 次询问，第 $k$ 次询问会给出 $S$ 的一个字符串 $S{l,r}$ ，请你求出有多少对 $(i, j)$，满足 $1 \le i < j \le n$，$i + 1 \lt 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}$。
输出格式
对于每个询问，输出一个整数表示合法的数对个数。
样例
input
5 2
00100
1 2
1 3output
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 · 10^5$，$1 \le l \le r \le n$。