后缀数组查询：给定子串，求其后缀的排名

后缀数组查询：给定子串，求其后缀的排名

给定一个字符串 s，求其后缀数组，并给出 m 个查询。每个查询给定一个子串 x = s[l..r]，求 x 的后缀 s[k..r] 在 s 的所有后缀中排名的位置。

输入格式

有多组测试数据。第一行包含一个整数 T，表示测试数据的组数。对于每组测试数据：

• 第一行包含两个整数 n 和 m (1≤n,m≤5×10⁴ ) - 字符串的长度和查询的数量。
• 第二行包含一个长度为 n 的字符串 s，只包含小写英文字母。
• 接下来 m 行，每行包含三个整数 l、r 和 k (1≤l≤r≤n,l≤k≤r)，表示一个查询。

保证所有测试数据中 n 的总和以及 m 的总和均不超过 5×10⁴。

输出格式

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

样例输入

1
5 2
banana
1 3 2
2 4 3

样例输出

4
2

解释

• s 的所有后缀按照字典序排序后的结果为：

  • a
  • ana
  • anana
  • banana
  • na
  • nana

• 第一个查询：l = 1, r = 3, k = 2，子串 x = s[1..3] = ban，x 的后缀 s[2..3] = an 在 s 的所有后缀中排名第 4 位。

• 第二个查询：l = 2, r = 4, k = 3，子串 x = s[2..4] = ana，x 的后缀 s[3..4] = na 在 s 的所有后缀中排名第 2 位。

提示

• 可以使用后缀数组来解决本题。
• 后缀数组是一个数组 sa，它存储了字符串 s 所有后缀的字典序排序后的下标。
• 通过后缀数组，可以快速找到一个子串的所有后缀在 s 的所有后缀中的排名。
• 可以使用二分查找来找到子串的排名。