struct SuffixArray {
    // 注意需要先进行init()操作， 使得s[0..n-1]都是[1, m)中的整数， s[n]=0
    //对字符s[0..n-1]建立后缀数组 s[]的长度是n, 要求是s[n]=0， s[0..n-1]>0
    // sa[i]表示第i小的后缀从字符串的第sa[i]个位置开始  sa[0]是0(结尾的最小特殊字符)
    // rank[i]表示字符串第i个位置开始的后缀是第rk[i]小的字符串
    // height[i]表示sa[i]和sa[i-1]所代表的字符串的公共前缀的长度
    static const int maxn = 100005;
    int sa[maxn], height[maxn], rank[maxn], n;
    int buc[maxn], t1[maxn], t2[maxn];
    int s[maxn];
    void init() {
        // 初始化s数组
    }
    void Suffix(int k) {
        REP(i,k,n)
        printf("%d ", s[i]);
        puts("");
        fflush(stdout);
    }
    inline bool cmp(int *r, int a, int b, int len) {
        return (r[a]==r[b]) && (r[a+len]==r[b+len]);
    }
    // 注意这里传入的n应该是 数组长度(0..n-1) +1
    void build(int n, int m=200) {
        this->n=n;
        int i, len, p, *x=t1, *y=t2;
        for (i=0; i<m; ++i)  buc[i]=0;
        for (i=0; i<n; ++i)  ++buc[x[i]=s[i]];
        for (i=1; i<m; ++i)  buc[i]+=buc[i-1];
        for (i=n-1; i>=0; --i)   sa[--buc[x[i]]]=i;
        for (len=1,p=1; p<n; m=p, len<<=1) {
            p=0;
            for (i=n-len; i<n; ++i)                  y[p++]=i;
            for (i=0; i<n; ++i)  if (sa[i]>=len)      y[p++]=sa[i]-len;
            for (i=0; i<m; ++i)  buc[i]=0;
            for (i=0; i<n; ++i)  ++buc[x[y[i]]];
            for (i=1; i<m; ++i)  buc[i]+=buc[i-1];
            for (i=n-1; i>=0; --i)   sa[--buc[x[y[i]]]]=y[i];
            swap(x, y);
            for (x[sa[0]]=0,i=1,p=1; i<n; ++i)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], len) ? p-1 : p++;
        }
        calHeight(n-1);
    }
    void calHeight(int n) {
        int i,j,k=0;
        for (i=1; i<=n; ++i)     rank[sa[i]]=i;
        for (i=0; i<n; height[rank[i++]]=k)
            for (k?--k:0, j=sa[rank[i]-1]; s[i+k]==s[j+k]; ++k);
    }
};