{"raw_statement":[{"iden":"statement","content":"\nA 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 suffixex of $s$ is a permutation $rank$ of integers from $1$ to $n$ such that $rank_{sa_i} = i$.\n\nKotori has a string $s=s_1s_2\\dots s_n$. She would like to ask $m$ queries. And in the $i$-th query, a substring $x=s[l_i..r_i]$ of $s$ is given, Kotori would like to know the rank of suffix $s[k_i..r_i]$ of $x$.\n\nNote $s[l..r]$ means the substring of $s$ which starts from the $l$-th position and ends at the $r$-th position, both inclusive.\n"},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe 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.\n\nThe second line contains a string $s$ of length $n$ consisting only of lowercase English letters.\n\nEach 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$) denoting a query.\n\nIt is guaranteed that neither the sum of $n$ or the sum of $m$ of all test cases will exceed $5 \\times 10^4$."},{"iden":"output","content":"For each query output one line containing one integer denoting the answer."}],"translated_statement":null,"sample_group":[["2\n10 4\nbaaabbabba\n2 8 3\n1 1 1\n2 3 2\n2 5 4\n20 3\ncccbccbadaacbbbcccab\n14 17 16\n3 20 17\n17 20 18\n","2\n1\n2\n3\n4\n15\n3\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}