#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + ;

typedef unsigned long long ull;

const ull mod = ;

ull p[maxn],h[maxn];

int sa[maxn],rank[maxn],height[maxn];

char str[maxn];

int n ;

ull get(int x,int y){

    return h[y] - h[x - ] * p[y - x + ];

}

int lcp(int x,int y){

    int l =  ,r = min(n - x + ,n - y + );

    while(l < r){

        int mid = (l + r + ) >> ;

        if(get(x,x + mid - ) != get(y,y + mid - )) r = mid - ;

        else l = mid;

    }

    return l;

}

bool cmp(int x , int y){

    int l = lcp(x,y);

    int av = x + l > n ? INT_MIN : str[x + l];

    int bv = y + l > n ? INT_MIN : str[y + l];

    return str[x + l] < str[y + l];

}

int main(){

    scanf("%s",str + );

    n = strlen(str + );

    p[] = ;

    for(int i = ;i <= n ;i ++){

        p[i] = mod * p[i-];

        h[i] = mod * h[i-] + str[i] - '' + ;

        sa[i] = i;

    }

    sort(sa + , sa +  + n , cmp);

    for(int i = ;i <= n ;i ++){

        height[i] = lcp(sa[i],sa[i-]);

    }

    for(int i = ;i <= n ;i ++) printf("%d%c",sa[i]-," \n"[i==n]);

    printf("0 ");

    for(int i = ;i <= n ;i ++) printf("%d%c",height[i]," \n"[i==n]);

    return ;

}

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + ;

struct DA{

    bool cmp(int *r,int a,int b,int l){

        return r[a]==r[b]&&r[a+l]==r[b+l];

    }

    int t1[maxn],t2[maxn],c[maxn];

    int rank[maxn],height[maxn],RMQ[maxn],mm[maxn];

    int best[][maxn];

    int r[maxn];

    int sa[maxn];

    int str[maxn];

    void da(int n,int m){

        n++;

        int i,j,p,*x=t1,*y=t2;

        for(i=;i<m;i++)c[i]=;

        for(i=;i<n;i++)c[x[i]=str[i]]++;

        for(i=;i<m;i++)c[i]+=c[i-];

        for(i=n-;i>=;i--)sa[--c[x[i]]]=i;

        for(j=;j<=n;j<<=){

            p=;

            for(i=n-j;i<n;i++)y[p++]=i;

            for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

            for(i=;i<m;i++)c[i]=;

            for(i=;i<n;i++)c[x[y[i]]]++;

            for(i=;i<m;i++)c[i]+=c[i-];

            for(i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];

            swap(x,y);

            p=;x[sa[]]=;

            for(i=;i<n;i++)

                x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

            if(p>=n)break;

            m=p;

        }

        int k=;

        n--;

        for(i=;i<=n;i++)rank[sa[i]]=i;

        for(i=;i<n;i++){

            if(k)k--;

            j=sa[rank[i]-];

            while(str[i+k]==str[j+k])k++;

            height[rank[i]]=k;

        }

    }

    void initRMQ(int n){

        for(int i=;i<=n;i++)RMQ[i]=height[i];

        mm[]=-;

        for(int i=;i<=n;i++)

            mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];

        for(int i=;i<=n;i++)best[][i]=i;

        for(int i=;i<=mm[n];i++)

        for(int j=;j+(<<i)-<=n;j++){

            int a=best[i-][j];

            int b=best[i-][j+(<<(i-))];

            if(RMQ[a]<RMQ[b])best[i][j]=a;

            else best[i][j]=b;

        }

    }

    int askRMQ(int a,int b){

        int t;

        t=mm[b-a+];

        b-=(<<t)-;

        a=best[t][a];b=best[t][b];

        return RMQ[a]<RMQ[b]?a:b;

    }

    int lcp(int a,int b){

        a=rank[a];b=rank[b];

        if(a>b)swap(a,b);

        return height[askRMQ(a+,b)];

    }

    void print(int n){

       // cout<<"sa[] ";

        for(int i=;i<=n;i++)cout<<sa[i]<<" ";cout<<endl;

        // cout<<"rank[] ";

        // for(int i=2;i<=n;i++)cout<<rank[i]<<" ";cout<<endl;

        //cout<<"height[] ";

        for(int i=;i<=n;i++)cout<<height[i]<<" ";cout<<endl;

    }

}AA,BB;

//n=8;

//* num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ }; 注意 num 最后一位为 0，其他 大于 0

//*rank[] = 4, 6, 8, 1, 2, 3, 5, 7, 0 ;rank[0 n-1] 为有效值，rank[n] 必定为 0 无效值

// *sa[] =  8, 3, 4, 5, 0, 6, 1, 7, 2 ;sa[1 n] 为有效值，sa[0] 必定为 n 是 无效值

//*height[]= 0, 0, 3, 2, 3, 1, 2, 0, 1 ;height[2 n] 为有效值

int main(int argc, char const *argv[])

{

    string str;

    cin >> str;

    for(int i = ;i < str.size();i ++) AA.str[i] = str[i] - '' + ;

    AA.str[str.size()] = ;

    AA.da(str.size() + ,);

    AA.print(str.size() + );

    return ;

}