아기의 첫 접미사 배열 문제

길이가 $n$인 문자열 $s$의 접미사 배열은 $1$부터 $n$까지의 정수로 이루어진 순열 $sa$이며, $s[sa_1..n], s[sa_2..n], \dots, s[sa_n..n]$이 $s$의 공백이 아닌 모든 접미사를 사전순으로 정렬한 목록이 되도록 하는 것이다. $s$의 접미사에 대한 순위 표는 $1$부터 $n$까지의 정수로 이루어진 순열 $rank$이며, $rank_{sa_i} = i$를 만족한다.

코토리에게 문자열 $s = s_1s_2\dots s_n$이 있다. 그녀는 $m$개의 질의를 하려고 한다. $i$번째 질의에서는 $s$의 부분 문자열 $x = s[l_i..r_i]$가 주어지고, 코토리는 $x$에서 접미사 $s[k_i..r_i]$의 순위를 알고 싶어 한다.

$s[l..r]$은 $s$의 $l$번째 위치에서 시작해 $r$번째 위치에서 끝나는 부분 문자열을 뜻하며, 양 끝을 모두 포함한다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 문자열의 길이 $n$과 질의의 개수 $m$이 주어진다 ($1 \le n, m \le 5 \times 10^4$).

둘째 줄에는 영어 소문자로만 이루어진 길이 $n$의 문자열 $s$가 주어진다.

이어지는 $m$개의 줄에는 각각 세 정수 $l_i$, $r_i$, $k_i$가 주어지며 ($1 \le l_i \le r_i \le n$, $l_i \le k_i \le r_i$), 이는 하나의 질의를 나타낸다.

모든 테스트 케이스의 $n$ 합과 $m$ 합은 각각 $5 \times 10^4$을 넘지 않는다.

각 질의마다 답을 한 줄에 정수 하나로 출력한다.