Background

Little M and Little B are a pair of good friends, and they really like hiking.

Problem Description

A mountain can be abstracted as a string $S$ of length $n$, containing only lowercase letters.

For a string $S$, we define $|S|$ as the length of the string, and $S_{L\ldots R}$ as the string formed by concatenating, from left to right, the $L$-th character to the $R$-th character in $S$.

Little M starts at position $i$, and she wants to reach the peak at position $k$, while Little B will help her. To do this, they need to perform a sequence of operations.

They must use the teleportation magic circle at position $p$ exactly once before all operations. By casting the spell, Little B's position can be changed to any $j$ satisfying $j \geq i$ and $S_{i \ldots j} = S_{p \ldots p + (j-i)}$. At the same time, they need to pay a cost of $n-j$. It is guaranteed that such a $j$ exists.

After that, suppose Little M and Little B are at positions $i$ and $j$, respectively. They may perform any number of times one of the following operations:

• Let Little M climb, i.e. set $i=i+1$ or $i=i-1$. If after this operation $i>j$, then set $j=i$.

• Let Little B climb, i.e. set $j=j+1$ or $j=j-1$. If after this operation $i>j$, then set $i=j$.

• Use "Spiral Ascension". Specifically, choose two indices $l$ and $r$ such that $S_{l \ldots r} = S_{i \ldots j}$, then set $i=l,j=r$.

For some reason, after each operation, it must be guaranteed that $1 \leq i , j \leq n$. Performing any one of the above operations costs $1$.

Hiking is tiring, so they want to know the minimum total cost needed to make Little M reach the peak, i.e. make $i=k$. Also, because they like hiking very much, they have many queries to ask you.

Input Format

The first line contains two integers $n$ and $q$, representing the length of the string $S$ and the number of queries.

The second line contains a string $S$ of length $n$, consisting only of lowercase letters.

The next $q$ lines each contain three integers $i,p$ and $k$, indicating Little M's position, the teleportation magic circle position, and the peak position.

Output Format

Output $q$ lines in total. The $i$-th line contains an integer, representing for the $i$-th query with given $i,p$ and $k$, the minimum total cost needed to make Little M reach the peak, i.e. make Little M's position $i=k$.

8 2
dacdaaaa
5 8 1
1 4 5

5
8

Hint

【Help and Hints】

To make it easier for contestants to test their code, this problem additionally provides an extra sample for contestants to use.

Sample Input Sample Output

【Sample Explanation】

For the first query in the sample, when using the teleportation spell, we can only set $j=5$, paying a cost of $8-5=3$. After that, first use the third type of operation once, choosing $l=2,r=2$ and setting $i=l,j=r$, then use the first type of operation once, setting $i-1$, and thus make $i=k$. The total cost is $5$.

For the second query, we can choose $j=2$, paying a cost of $8-2=6$, then use the third type of operation once, choosing $l=4,r=5$ and setting $i=l,j=r$, and then perform the first type of operation once, setting $i+1$, to make $i=k$. The total cost is $8$.

【Constraints】

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1 \leq n,q \leq 3\times 10^4$, and $S$ contains only lowercase letters.

Property $S_1$ is: for a given $p$, the $j$ that satisfies the condition is unique.

Translated by ChatGPT 5