题目背景

小 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

提示

【帮助与提示】

为方便选手测试代码，本题额外提供一组附加样例供选手使用。

样例输入 样例输出

---

【样例解释】

对于样例的第一组询问，使用传送法术时，只能令 $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$		无	$3$	1s
Subtask 2	$80$			$14$
Subtask 3	$2 \times 10^4$		$S$ 中仅包含a	$8$	3s
Subtask 4			$S_1$	$7$
Subtask 5	$400$		无	$9$	1s
Subtask 6	$2\times 10^4$	$2 \times 10^4$	所有询问的 $k$ 相同	$10$	3s
Subtask 7	$10^3$		无		2s
Subtask 8	$1.5 \times 10^4$			$11$	3s
Subtask 9	$3 \times 10^4$			$28$

性质 $S_1$ 是，对于给定的 $p$，满足条件的 $j$ 唯一。