Suffix Array Rank Queries

A suffix array for a string \(s\) of length \(n\) is a permutation \(sa\) of integers from \(1\) to \(n\) such that the list of non-empty suffixes \(s[sa_1..n], s[sa_2..n], \dots, s[sa_n..n]\) is sorted in lexicographical order. The rank table for the 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 wants to answer \(m\) queries. In the \(i\)-th query, you are given three integers \(l_i\), \(r_i\), and \(k_i\). Let \(x=s[l_i..r_i]\) be a substring of \(s\). Your task is to determine the rank (1-indexed) of the suffix \(x[k_i-l_i+1..|x|]\) in the sorted list of all non-empty suffixes of \(x\).

Note: For a string \(s\), the notation \(s[l..r]\) denotes the substring that starts at the \(l\)-th character and ends at the \(r\)-th character (both inclusive).

inputFormat

The input begins with a string \(s\) on the first line. The second line contains an integer \(m\), the number of queries. Each of the following \(m\) lines contains three integers \(l\), \(r\), and \(k\) separated by spaces, representing a query.

It is guaranteed that \(1 \le l \le k \le r \le |s|\).

outputFormat

For each query, output a single line with one integer: the rank of the specified suffix of the substring \(x\), when all non-empty suffixes of \(x\) are sorted in lexicographical order.

sample

banana
3
1 6 1
1 6 3
2 4 3

4
6
3