T163813 破坏子串

记 $S_{[L \ldots R]}$ 为 字符串 $S$ 从第 $L$ 个字符到第 $R$ 个字符顺次连接形成的字符串。 给定一仅包含小写英文字母的字符串 $S$，你可以向其中插入任意数量的 $\texttt{*}$ 字符。 现有若干组询问，每次询问将输入一对 $L,R$，表示询问对于字符串 $T = S_{[L \ldots R]}$ ，求至少需要向 $S$ 中插入多少个 $\texttt{*}$ 字符，才能使串 $T$ 不再是 $S$ 的子串。特别地，若该要求无法完成，请输出 $-1$。

无

无

**【样例解释 #1】** 下面是样例 #1 的解释： 对于第一组询问，只需在 $\texttt{a}$ 和 $\texttt{k}$ 之间插入一个 $\texttt{*}$。 对于第二组询问，可以插入两个 $\texttt{*}$ 将 $S$ 变成 $\texttt{io*iaki*oi}$。 ---- **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $n \leq$ | $q \leq$ | 特殊限制 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $6$ | $6$ | 无 | $6$ | | $2$ | $5 \times {10}^3$ | $5 \times {10}^3$ | 无 | $16$ | | $3$ | ${10}^5$ | ${10}^5$ | 特殊性质 A | $11$ | | $4$ | $3 \times {10}^4$ | $3 \times {10}^4$ | 特殊性质 B | $9$ | | $5$ | ${10}^5$ | ${10}^5$ | 特殊性质 C | $18$ | | $6$ | ${10}^5$ | ${10}^5$ | 无 | $40$ | 特殊性质 A：$S$ 中仅包含 $\texttt{a}$。 特殊性质 B：$\sum (R - L) \leq {10}^5$。 特殊性质 C：所有查询的子串满足：它的任何非空后缀和前缀不相等。 对于所有测试点，保证 $n$ 为正整数且 $3 \leq n, q \leq {10}^5$，$1 \leq L \leq R \leq n$，$S$ 中仅包含小写字母。