『MdOI R2』Little Goth

小 M 和小 B 是一对好朋友，她们很喜欢爬山。

山可以抽象为一个长为 $n$ 的字符串 $S$，串中仅包含小写字母。 对于一个字符串 $S$，我们定义 $|S|$ 表示串的长度，$S_{L\ldots R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。 小 M 一开始的位置是 $i$，她想要到达位置在 $k$ 处的山顶，而小 B 则要帮助她。为此，她们需要进行一系列操作。 她们**必须**在所有操作之前使用**一次**位于 $p$ 处的传送法阵，通过施展法术，可以使小 B 的位置变为任意满足 $j \geq i$ 且 $S_{i \ldots j} = S_{p \ldots p + (j-i)}$ 的 $j$。但同时，她们需要付出 $n-j$ 的代价。保证这样的 $j$ 存在。 之后，假设小 M ，小 B 的位置分别为 $i$ 和 $j$，她们可以任意次进行下列操作中的一种： - 让小 M 爬，即令 $i=i+1$ 或 $i = i-1$。如果这一步操作之后 $i>j$，则 令 $j=i$。 - 让小 B 爬，即令 $j=j+1$ 或 $j=j-1$。如果这一步操作之后 $i>j$，则令 $i=j$。 - 使用螺旋升天，具体而言，选择两个下标 $l$ 和 $r$，满足 $S_{l \ldots r} = S_{i \ldots j}$，然后令 $i=l,j=r$。 出于某些原因，任何一次操作结束后，需要保证 $1 \leq i , j \leq n$。进行一次上述任意一种操作，都需要付出 $1$ 的代价。 爬山是很累的，因此她们想知道，至少需要付出多少代价才能让小 M 到达山顶，也就是让 $i=k$。又因为她们很喜欢爬山，她们有很多组询问要问你。

第一行两个整数，$n$ 和 $q$，表示串 $S$ 的长度和询问的个数。 第二行一个长度为 $n$ 的字符串 $S$，仅包含小写字母。 接下来 $q$ 行，每行三个整数 $i,p$ 和 $k$，表明小 M 的位置，传送法阵位置和山顶的位置。

共 $q$ 行，第 $i$ 行一个整数，表示对于第 $i$ 个询问给定的 $i,p$ 和 $k$，至少需要付出多少代价，才能让小 M 到达山顶，也就是，让小 M 的位置 $i=k$。

8 2
dacdaaaa
5 8 1
1 4 5

5
8

【帮助与提示】 为方便选手测试代码，本题额外提供一组附加样例供选手使用。 [样例输入](https://www.luogu.com.cn/paste/j7u8z9ir) [样例输出](https://www.luogu.com.cn/paste/fh19p0a4) -------- 【样例解释】 对于样例的第一组询问，使用传送法术时，只能令 $j=5$，付出 $8-5=3$ 的代价。之后，首先使用一次第三种操作，选择 $l=2,r=2$，令 $i=l,j=r$，然后使用一次第一种操作，令 $i-1$，即可使 $i=k$，一共付出 $5$ 的代价。 对于第二组询问，可以选择 $j=2$，付出 $8-2=6$ 的代价，然后使用一次第三种操作，选取 $l=4,r=5$ 并使 $i=l,j=r$，然后进行一次第一种操作，令 $i+1$ 即可使 $i=k$。一共付出 $8$ 的代价。 --- 【数据范围】 **本题采用捆绑测试。** 对于全部数据，保证 $1 \leq n,q \leq 3\times 10^4$，$S$ 中仅包含小写字母。 | 子任务编号 | $n\leq$ | $q \leq$ | 特殊性质 | 分值 | 时间限制 | | :--------: | :---------------: | :---------------: | :-----------------: | :--: | :------: | | Subtask 1 | $15$ | $15$ | 无 | $3$ | 1s | | Subtask 2 | $80$ | $80$ | 无 | $14$ | 1s | | Subtask 3 | $2 \times 10^4$ | $2 \times 10^4$ | $S$ 中仅包含`a` | $8$ | 3s | | Subtask 4 | $2 \times 10^4$ | $2 \times 10^4$ | $S_1$ | $7$ | 3s | | Subtask 5 | $400$ | $400$ | 无 | $9$ | 1s | | Subtask 6 | $2\times 10^4$ | $2 \times 10^4$ | 所有询问的 $k$ 相同 | $10$ | 3s | | Subtask 7 | $10^3$ | $10^3$ | 无 | $10$ | 2s | | Subtask 8 | $1.5 \times 10^4$ | $1.5 \times 10^4$ | 无 | $11$ | 3s | | Subtask 9 | $3 \times 10^4$ | $3 \times 10^4$ | 无 | $28$ | 3s | 性质 $S_1$ 是，对于给定的 $p$，满足条件的 $j$ 唯一。