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

constexpr int MAXN = 1e6 + 5;

int n, m = 127;
string s;
int sa[MAXN], rk[MAXN], h[MAXN], cnt[MAXN], id[MAXN], height[MAXN], key1[MAXN], p;

int oldrk[MAXN * 2];

bool cmp(int x, int y, int w) {
    return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void solve() {
    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i]]++;

    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];

    for (int i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;

    for (int w = 1;; w <<= 1, m = p) {
        p = 0;

        for (int i = n; i > n - w; i--)
            id[++p] = i;

        for (int i = 1; i <= n; i++)
            if (sa[i] > w)
                id[++p] = sa[i] - w;

        memset(cnt, 0, sizeof cnt);

        for (int i = 1; i <= n; i++)
            cnt[key1[i] = rk[id[i]]]++;

        for (int i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1];

        for (int i = n; i >= 1; i--)
            sa[cnt[key1[i]]--] = id[i];

        memcpy(oldrk + 1, rk + 1, n * sizeof(int));
        p = 0;

        for (int i = 1; i <= n; i++) {
            if (cmp(sa[i], sa[i - 1], w))
                rk[sa[i]] = p;
            else
                rk[sa[i]] = ++p;
        }

        if (p == n)
            return;
    }

    for (int i = 1, k = 0; i <= n; i++) {
        if (rk[i] == 0)
            continue;

        if (k)
            k--;

        while (s[i + k] == s[sa[rk[i] - 1] + k])
            k++;

        height[rk[i]] = k;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> s;
    n = s.size();
    s = " " + s;
    solve();

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

    cout << endl;

    return 0;
}