My approach is very brute_force,and it is an online algorithm:

First build suffix array and lcp[], for each query [li,ri],lets find the nearest right rank of position (lm=li), in the position,interval [li+1,ri],we denote this positon,pos,then find lcp=lcp[li][pos], then lm=max(pos, ri-lcp+1), in order to speed up to find the first yes postion, we must deal with parttern str=AAAAAAAA+prefix(A) (this is not legal answer,but currenc lcp value is max.),A is a string,if this pattern is occur we directly get pos=max(pos,len(str)-len(A))..

with this speed up we can get the first yes positon (pos+lcp>ri) we only jump log(n) times, but this is not the final answer, this is a lcp_max() answer but not the left most answer, so we must continue to go left, denote lm=max(lm,ri-lcp+1),rm=min(rm,sa[pos]-1), similarly there may occur str=AAAAAAA+prefix(A) (this is a legal answer), we can binary_search to find the left most legal answer (jump lenth(A) positon),and denote rm with this left most legal postion.

this is an online algorithm and I have test for each query the maximum iteration times is not exceed 40, so maybe this is an O(q*Log(n)^log(n)) algorithm...