class SuffixArray {
public:
    int maxN=int(1e6),n,gap;
    int *sa,*pos,*tmp,*lcp;
    string s;
    SuffixArray (string S) {
        s=S;
        n=s.length();
        sa=new int[maxN];
        pos=new int[maxN];
        tmp=new int[maxN];
        lcp=new int[maxN];
        gap=1;
        memset(sa,0,sizeof(sa));
        memset(pos,0,sizeof(pos));
        memset(tmp,0,sizeof(tmp));
        memset(lcp,0,sizeof(lcp));
    }
    bool sufCmp (int i, int j) {
        if (pos[i] != pos[j]) {
            return pos[i] < pos[j];
        }
        i += gap;
        j += gap;
        return (i < n and j < n) ? pos[i] < pos[j] : i > j;
    }
    void buildSA () {
        for (int i=0; i<n; i++) {
            sa[i]=i;
            pos[i]=s[i];
        }
        for (gap=1; ; gap*=2) {
            sort(sa,sa+n,sufCmp);
            for (int i=0; i<n-1; i++) {
                tmp[i+1]=tmp[i]+sufCmp(sa[i],sa[i+1]);
            }
            for (int i=0; i<n; i++) {
                pos[sa[i]]=tmp[i];
            }
            if (tmp[n-1]==n-1) {
                break;
            }
        }
    }
    ~SuffixArray () {
        delete []sa;
        delete []pos;
        delete []tmp;
        delete []lcp;
    }
};