#include <iostream>
#include <bits/stdc++.h>

using namespace std;
string s;
int n;
vector<int> cnt;
vector<int> p;
vector<int> c;
int p_temp[10000000];
int c_temp[10000000];

int main() {
    cin >> s;
    s += '$';
    n = s.size();
    cnt.resize(27);
    p.resize(s.size());
    c.resize(s.size());
    for (size_t j = 0; j < s.size(); ++j) {
        if (s[j] == '$') {
            ++cnt[0];
        } else {
            ++cnt[s[j] - 'a' + 1];
        }
    }
    for (size_t j = 1; j < 27; ++j) {
        cnt[j] += cnt[j - 1];
    }
    for (size_t j = 0; j < s.size(); ++j) {
        p[--cnt[max(0, s[j] - 'a' + 1)]] = j;
    }
    c[p[0]] = 0;
    int class_equiv = 0;
    for (size_t j = 1; j < s.size(); ++j) {
        if (s[p[j]] != s[p[j - 1]]) {
            ++class_equiv;
        }
        c[p[j]] = class_equiv;
    }
    ++class_equiv;
    for (int i = 0; (1 << i) < n; ++i) {
        for (int j = 0; j < n; ++j) {
            p_temp[j] = (p[j] - (1 << i) + n) % n;
        }
        cnt.resize(class_equiv);
        fill(cnt.begin(), cnt.end(), 0);
        for (int j = 0; j < n; ++j) {
            ++cnt[c[p_temp[j]]];
        }
        for (int j = 1; j < class_equiv; ++j) {
            cnt[j] += cnt[j - 1];
        }
        for (int j = n - 1; j >= 0; --j) {
            p[--cnt[c[p_temp[j]]]] = p_temp[j];
        }
        c_temp[p[0]] = 0;
        class_equiv = 0;
        for (int j = 1; j < n; ++j) {
            int m1 = (p[j] + (1 << i)) % n;
            int m2 = (p[j - 1] + (1 << i)) % n;
            if (c[p[j]] != c[p[j - 1]] || c[m1] != c[m2])
                ++class_equiv;
            c_temp[p[j]] = class_equiv;
        }
        ++class_equiv;
        for (int j = 0; j < n; ++j) {
            c[j] = c_temp[j];
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << p[i] + 1 << " ";
    }
    vector<int> lcp;
    vector<int> pos;
    lcp.resize(n);
    pos.resize(n);
    for (int i = 0; i < n; ++i) {
        pos[p[i]] = i;
    }
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (k > 0)
            --k;
        if (pos[i] == n - 1) {
            lcp[n - 1] = -1;
            k = 0;
            continue;
        } else {
            int j = p[pos[i] + 1];
            while (max(i + k, j + k) < n && s[i + k] == s[j + k]) {
                ++k;
            }
            lcp[pos[i]] = k;
        }
    }
    cout << endl;
    for (int i = 1; i < n - 1; ++i) {
        cout << lcp[i] << " ";
    }
}