s sorted in lexicographical order. The rank table for suffixex of. s is given, Kotori would like to know the rank of suffix
A suffix array for string s s of length n n is a permutation sa sa of integers from 1 1 to n n such that s[sa_1.. n], s[sa_2..n], dots, s[sa_n..n] s[sa 1 ..n],s[sa 2 ..n],…,s[sa n ..n] is the list of non-empty suffixes of s s sorted in lexicographical order. The rank table for suffixex of s s is a permutation rank rank of integers from 1 1 to n n such that rank_{sa_i} = i rank sa i =i. Kotori has a string s=s_1s_2dots s_n s=s 1 s 2 …s n . She would like to ask m m queries. And in the i i-th query, a substring x=s[l_i..r_i] x=s[l i ..r i ] of s s is given, Kotori would like to know the rank of suffix s[k_i..r_i] s[k i ..r i ] of x x. Note s[l..r] s[l..r] means the substring of s s which starts from the l l-th position and ends at the r r-th position, both inclusive.
