Baby's First Suffix Array Problem

A suffix array for string $s$ of length $n$ is a permutation $sa$ of integers from $1$ to $n$ such that $s[sa_1..n], s[sa_2..n], \dots, s[sa_n..n]$ is the list of non-empty suffixes of $s$ sorted in lexicographical order. The rank table for suffixes of $s$ is a permutation $rank$ of integers from $1$ to $n$ such that $rank_{sa_i} = i$.

Kotori has a string $s = s_1s_2\dots s_n$. She would like to ask $m$ queries. In the $i$-th query, a substring $x = s[l_i..r_i]$ of $s$ is given, and Kotori would like to know the rank of the suffix $s[k_i..r_i]$ of $x$.

$s[l..r]$ means the substring of $s$ that starts at the $l$-th position and ends at the $r$-th position, both inclusive.

There are multiple test cases. The first line of the input contains an integer $T$, the number of test cases. Each test case is as follows.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \times 10^4$), the length of the string and the number of queries.

The second line contains a string $s$ of length $n$ consisting only of lowercase English letters.

Each of the next $m$ lines contains three integers $l_i$, $r_i$, and $k_i$ ($1 \le l_i \le r_i \le n$, $l_i \le k_i \le r_i$), describing a query.

The sum of $n$ over all test cases and the sum of $m$ over all test cases do not exceed $5 \times 10^4$.

For each query, output one line containing one integer, the answer.