对于一个字符串 S ，我们定义 |S| 表示 S 的长度。
接着，我们定义 S_i 表示 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} 。
对于每个询问，输出一个整数表示合法的数对个数。
5 2 00100 1 2 1 3
5 1
对于所有测试数据， 1 \le n \le 10^5 ， 1 \le q \le 3 · 10^5 ， 1 \le l \le r \le n 。
