【题目描述】：
    pps又开始dota视频直播了！
    一群每天被pps虐的蒟蒻决定学习pps的操作技术，他们把pps在这局放的技能记录了下来，每个技能用一个字符表示。经过研究，蒟蒻们发现字典序更大的连招威力更大。于是所有蒟蒻都想学习pps最强的连招。但是他们太弱了，不能学会整个视频里的连招，只能学会陈老师一段区间间内的连招，可是这个他们求不出，于是只好向你求助。为了蒟蒻们不再被pps虐（怎么可能），请你帮帮他们。
简化题意：
    给你一个字符串，每次询问你一段区间的字典序最大的子串。
【题目解法】：
    考虑离线处理
    设右端点为r，然后用set维护[l,r] (l<=r)的答案
    容易发现[l,r]的答案随着l的增加单调不减
    因此在set里面lower_bound一下就好了
    性质+：在set里面，任意两个位置i<j满足s[i,r]>s[j,r]
    考虑r->r+1是set的变化
    考虑两个后缀有s[i,n]>s[j,n] (i<j)
    显然有s[i,k]>s[j,k] (k>=j) 因此j不可能成为答案
    因此考虑那些s[i,n]<s[j,n] (i<j)的后缀
    设他们的lcp=L，显然：
    1.在(j<=k<j+L)的时候有 s[i,k]>s[j,k]
    2.在(k>=j+L)的时候有 s[i,k]<s[j,k]
    根据性质可知当r=j+L的时候需要把i删去
    我们成这样的情况为i伴随j（题解里面是这么说的）
    同时我们需要递归的把伴随i的，伴随伴随i的，...全部递归删去
    考虑证明：
    假设k伴随i，i伴随j
    1.k已经被删去，那么就不用管了
    2.k未被删去，显然有s[k,n]<s[i,n]<s[j,n]即k伴随j
      由于k未被删去有：k+lcp(s[k,n],s[i,n])>j+lcp(s[i,n],s[j,n])
      因此k与j的lcp就是lcp(s[i,n],s[j,n])，因此当r=j+lcp(s[i,n],s[j,n]) k要被删去
    得证
    最后考虑对于每一个点我们只需要找到最早被删去的时刻
    对后缀维护一个单调栈，每次加入后缀s[r+1,n]的时候和栈尾元素比较即可
    每个点只会被删除一次，插入一次
    复杂度O(N log N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
const int N=200005;
struct node {int l,r,id;} a[N];
int n,m,ans[N],stack[N]; char s[N]; set<int> S;
bool v[N]; vector<int> del[N],b[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline bool cmp(const node &a,const node &b) {return a.r<b.r;}
void init()
{
    scanf("%s",s+1); n=strlen(s+1); m=getint();
    for (int i=1; i<=m; i++) a[i].l=getint(),a[i].r=getint();
    for (int i=1; i<=m; i++) a[i].id=i; sort(a+1,a+m+1,cmp);
}
namespace Suffix_Array
{
    int rank[N],sa[N],x[N],y[N],m,c[N],tot,f[21][N];
    void init()
    {
        for (int i=1; i<=n; i++) c[x[i]=s[i]]++;
        for (int i=1; i<=n; i++) m=max(m,x[i]);
        for (int i=1; i<=m; i++) c[i]+=c[i-1];
        for (int i=1; i<=n; i++) sa[c[x[i]]--]=i;
    }
    void build()
    {
        for (int k=1; k<n; k*=2)
        {
            tot=0; for (int i=n-k+1; i<=n; i++) y[++tot]=i;
            for (int i=1; i<=n; i++) if (sa[i]>k) y[++tot]=sa[i]-k;
            for (int i=0; i<=m; i++) c[i]=0;
            for (int i=1; i<=n; i++) c[x[i]]++;
            for (int i=1; i<=m; i++) c[i]+=c[i-1];
            for (int i=n; i>=1; i--) sa[c[x[y[i]]]--]=y[i]; m=0;
            for (int i=1; i<=n; i++)
            {
                int u=sa[i],v=sa[i-1];
                if (i==1) {y[u]=++m; continue;}
                if ((x[u]!=x[v])||(x[u+k]!=x[v+k])) ++m;
                y[u]=m;
            }
            if (m>=n) break;
            for (int i=1; i<=n; i++) x[i]=y[i];
        }
        for (int i=1; i<=n; i++) rank[sa[i]]=i;
    }
    void solve()
    {
        int h=0;
        for (int i=1; i<=n; i++)
        {
            if (rank[i]==1) continue; int j=sa[rank[i]-1];
            for (;(j+h<=n)&&(i+h<=n)&&(s[i+h]==s[j+h]);h++);
            f[0][rank[i]]=h; if (h>0) h--;
        }
        for (int i=1; i<=20; i++)
            for (int j=1; j<=n; j++)
            {
                if (j+(1<<i)-1>n) break;
                f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
            }
    }
    inline int ask(int l,int r)
    {
        l=rank[l]; r=rank[r]; if (l>r) swap(l,r);
        l++; int k=(int)(log(r-l+1)/log(2));
        return min(f[k][l],f[k][r-(1<<k)+1]);
    }
}
void dfs(int x)
{
    if (v[x]) return; v[x]=true; S.erase(x);
    int size=b[x].size();
    for (int i=0; i<size; i++) dfs(b[x][i]);
}
void solve()
{
    int top=0;
    for (int i=1; i<=n; i++) del[i].clear(),b[i].clear();
    for (int i=1,now=1; i<=n; i++)
    {
        for (;top;top--)
        {
            int now=stack[top],len=Suffix_Array::ask(now,i);
            if (s[now+len]>s[i+len]) break;
            del[i+len].push_back(now); b[i].push_back(now);
        }
        stack[++top]=i; S.insert(i); int size=del[i].size();
        for (int j=0; j<size; j++) dfs(del[i][j]);
        for (;(now<=m)&&(a[now].r==i);now++) ans[a[now].id]=(*S.lower_bound(a[now].l));
    }
    for (int i=1; i<=m; i++) printf("%d\n",ans[i]);
}
int main()
{
    init();
    Suffix_Array::init();
    Suffix_Array::build();
    Suffix_Array::solve();
    solve();
    return 0;
}