C. Sorting Substrings

#include <bits/stdc++.h>
using namespace std;

typedef pair<int , int> ii;
#define S second
#define F first

vector< ii > Seg;
string s;
int n ,q;

string Read(){
    const int MaxN = 4e5 + 5e2;
    static char Buff[MaxN];
    scanf("\n%s" ,Buff);
    return Buff;
}

string SubStr(string &Str ,int Start ,int Len = 1e9){
    string Res;

    int N = (int)Str.size();
    Len   = max(0 ,Len);
    Start = max(0 ,Start);

    for(int i = Start ; (i < N && i < Start + Len) ; i++)
        Res += Str[i];
    return Res;
}

void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n){
    int N = max(300 ,n);
    vector< int > Cnt(N ,0);
    vector< int > tempSA(n);

    for(int i = 0 ; i < n ; i++)
        Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;

    for(int i = 0, sum = 0 ; i < N ; i++){
        int t = Cnt[i];
        Cnt[i] = sum;
        sum += t;
    }

    for(int i = 0 ; i < n ; i++)
        tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];

    SA = tempSA;
}

void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n){
    CountSort(SA ,RA ,s ,n);
    CountSort(SA ,RA ,f ,n);
}

vector< int > ConstructSA(string &s ,int n){
    vector< int > tempRA(n ,0);
    vector< int > SA(n ,0) ,RA(n ,0);

    for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
    for(int i = 0 ; i < n ; i++) SA[i] = i;

    for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 ){
        RadixSort(SA ,RA ,k ,0 ,n);

        int r = tempRA[ SA[0] ] = 0;
        for(int i = 1 ; i < n ; i++){
            bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
            bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
                          RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
            tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
        }

        RA = tempRA;
    }

    return SA;
}

vector< int > GetLCP(vector< int > &Suff ,string &s ,int n){
    vector< int > PLCP(n);
    vector< int > LCP(n);
    vector< int > Phi(n);

    Phi[ Suff[0] ] = -1;
    for(int i = 1 ; i < n ; i++) Phi[ Suff[i] ] = Suff[i - 1];

    for(int i = 0 ,Len = 0 ; i < n ; i ++){
        if( Phi[i] != -1 ){
            while( (i + Len < n) && (Phi[i] + Len < n)
                  && (s[i + Len] == s[Phi[i] + Len]) )
                    Len += 1;
            PLCP[i] = Len;
            Len = max(Len - 1 ,0);
        } else PLCP[i] = 0;
    }

    for(int i = 0 ; i < n ; i++) LCP[i] = PLCP[ Suff[i] ];
    return LCP;
}

int Search(vector< int > &Suff ,vector< int > &LCP ,vector< int > &Pos ,string &s ,int n ,int L ,int R) {
    int Len = R - L + 1 ,Idx = Pos[L - 1];
    while( LCP[Idx] >= Len ) Idx -= 1;
    return Idx;
}

inline bool Sorter(ii &a ,ii &b){
    int LenA = a.S - a.F + 1;
    int LenB = b.S - b.F + 1;

    if( LenA  < LenB ) return true;
    if( LenA == LenB ){
        if( a.F  < b.F ) return true;
        if( a.F == b.F && a.S < b.S ) return true;
    }

    return false;
}

int main() {
    n = (int)(s = Read() + ' ').size();

    scanf("%d" ,&q);             Seg.resize( q );
    for(auto &i : Seg) scanf("%d%d" ,&i.F ,&i.S);

    vector< int > Suff = ConstructSA(s ,n);
    vector< int > LCP = GetLCP(Suff ,s ,n);

    vector< int > Pos(n);
    for(int i = 0 ; i < n ; i++) Pos[ Suff[i] ] = i;

    map< ii , pair<bool , int> > FirstOcc;
    map<int , vector< ii > > Cnt;
    for(auto i : Seg){
            if( !FirstOcc[i].F ){
                    FirstOcc[i].F = true;
                    FirstOcc[i].S = Search(Suff ,LCP ,Pos ,s ,n ,i.F ,i.S);
            }
            Cnt[ FirstOcc[i].S ].push_back(i);
    }

    vector< ii > Ans;
    for(auto &i : Cnt){
        sort(i.S.begin() ,i.S.end() ,Sorter);
        for(auto j : i.S) Ans.push_back(j);
    }

    for(auto i : Ans) printf("%d %d\n" ,i.F ,i.S);
    return 0;
}