#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define endl '\n'
//#define int long long

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 5000;
const int M = 32;
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const int P = 1336;
const ld eps = 0.000000001;
const int inf = 1e9;

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

int g[M][N], a[N], p[N], lcp[N], lc[N];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    string s;
    getline(cin, s);
    int n = s.size();
    vector < pair <int, int> > v;
    for(int i = 0; i<n; i++)
    {
        v.pb({int32_t(s[i]) - 31, i});
    }
    sort(v.begin(), v.end());
    int uk = 0;
    for(int i = 0; i<v.size(); i++)
    {
        if (!(i && v[i].F == v[i-1].F)) uk++;
        g[0][v[i].S] = uk;
    }
    int m = 1;
    while ((1 << m) < n) m++;
    for(int j = 1; j <= m; j++)
    {

        vector < pair < pair <int, int>, int> > b;
        int len = (1 << j); len /= 2;
        for(int i = 0; i<n; i++)
        {
            if (i + len > n) b.pb({{g[j-1][i], 0}, i});
            else b.pb({{g[j-1][i], g[j-1][i+len]}, i});
        }
        sort(b.begin(), b.end());
        uk = 0;
        for(int i = 0; i<b.size(); i++)
        {
            if (!(i && b[i].F == b[i-1].F)) uk++;
            g[j][b[i].S] = uk;
        }
    }
    for(int i = 0; i<n; i++)
    {
        a[g[m][i]-1] = i;
    }
    for(int i = 0; i<n; i++)
    {
        p[i] = a[g[m][i]];
        cout << p[i] << " ";
    }
    for(int i = 0; i<n; i++)
    {
        if (i) lc[i] = max(0, lc[i-1] - 1);
        while (i + lc[i] < s.size() && p[i] + lc[i] < s.size() && s[i + lc[i]] == s[p[i] + lc[i]])
        {
            lc[i]++;
        }
        lcp[g[m][i]-1] = lc[i];
    }
    cout << endl;

    for(int i = 0; i<n; i++)
    {
        cout << lcp[i] << " ";
    }


}