#include <cstdio>
#include <cstring>
#include <cstdlib>

#define F(i, a, b) for (register int i = (a); i <= (b); i++)
#define D(i, a, b) for (register int i = (a); i >= (b); i--)

const int N = 50005;

char s[N]; int n;
int rk[N], sa[N], ht[N];

namespace Output {
    const int S = 1000000; char s[S]; char *t = s;
    inline void Print(int x) {
        if (x == 0) *t++ = ‘0‘;
        else {
            static int a[65]; int n = 0;
            for (; x > 0; x /= 10) a[++n] = x%10;
            while (n > 0) *t++ = ‘0‘+a[n--];
        }
        *t++ = ‘ ‘;
    }
    inline void Flush(void) { fwrite(s, 1, t-s, stdout); }
}
using Output::Print;

void Prework(void) {
    static int sum[N], trk[N], tsa[N]; int m = 500;
    F(i, 1, n) sum[rk[i] = s[i]]++;
    F(i, 1, m) sum[i] += sum[i-1];
    D(i, n, 1) sa[sum[rk[i]]--] = i;
    rk[sa[1]] = m = 1;

    F(i, 2, n) rk[sa[i]] = (s[sa[i]] != s[sa[i-1]] ? ++m : m);
    for (int j = 1; m != n; j <<= 1) {
        int p = 0; F(i, n-j+1, n) tsa[++p] = i; F(i, 1, n) if (sa[i] > j) tsa[++p] = sa[i]-j;
        F(i, 1, n) sum[i] = 0, trk[i] = rk[i];
        F(i, 1, n) sum[rk[i]]++;
        F(i, 1, m) sum[i] += sum[i-1];
        D(i, n, 1) sa[sum[trk[tsa[i]]]--] = tsa[i];
        rk[sa[1]] = m = 1;
        F(i, 2, n) {
            if (trk[sa[i]] != trk[sa[i-1]] || trk[sa[i]+j] != trk[sa[i-1]+j]) m++;
            rk[sa[i]] = m;
        }
    }

    m = 0;
    F(i, 1, n) {
        if (m > 0) m--;
        while (s[i+m] == s[sa[rk[i]-1]+m]) m++;
        ht[rk[i]] = m;
    }
}

int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("xsy1621.in", "r", stdin);
        freopen("xsy1621.out", "w", stdout);
    #endif

    scanf("%s", s+1); n = strlen(s+1);

    Prework();

    F(i, 1, n) Print(rk[i]); *(Output::t++) = ‘\n‘;
    F(i, 1, n) Print(ht[i]); *(Output::t++) = ‘\n‘;
    Output::Flush();

    return 0;
}