Description

对于长度为 $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$ 。

小鸟 Kotori 有一个字符串 $s = s_1s_2\dots s_n$ 。她想要进行 $m$ 次询问。在第 $i$ 次询问中，会给出 $s$ 的一个子串 $x = s[l_i..r_i]$ ，Kotori 想要知道 $x$ 的后缀 $s[k_i..r_i]$ 的排名。

注意，$s[l..r]$ 表示 $s$ 的从第 $l$ 个位置开始到第 $r$ 个位置结束的子串（包括第 $l$ 个和第 $r$ 个位置）。

Input Format

有多组测试数据。输入的第一行包含一个整数 $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$ 。

Output Format

对于每次询问，输出一行，包含一个整数，表示答案。

2
10 4
baaabbabba
2 8 3
1 1 1
2 3 2
2 5 4
20 3
cccbccbadaacbbbcccab
14 17 16
3 20 17
17 20 18

2
1
2
3
4
15
3

Hint

注意

题面翻译由 Doubao 提供。