#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 3e5 + 10;
const ull BASE = 131;

string s;
int n;
int sa[MAXN], rk[MAXN], height[MAXN];
ull h[MAXN], p[MAXN];

// 计算哈希值
ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

// 比较两个后缀的字典序
bool cmp(int a, int b) {
    int l = 0, r = n - max(a, b);
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (get_hash(a + 1, a + mid) == get_hash(b + 1, b + mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    if (a + l >= n || b + l >= n) {
        return a > b;
    }
    return s[a + l] < s[b + l];
}

void get_sa() {
    // 初始化哈希数组
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * BASE + s[i - 1] - 'a' + 1;
        p[i] = p[i - 1] * BASE;
        sa[i - 1] = i - 1;
    }
    
    // 使用自定义比较函数排序
    sort(sa, sa + n, cmp);
    
    // 计算rank数组
    for (int i = 0; i < n; i++) {
        rk[sa[i]] = i;
    }
}

void get_height() {
    height[0] = 0;
    for (int i = 0, k = 0; i < n; i++) {
        if (rk[i] == 0) {
            height[rk[i]] = 0;
            continue;
        }
        if (k) k--;
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> s;
    n = s.size();
    
    get_sa();
    get_height();
    
    // 输出SA数组
    for (int i = 0; i < n; i++) {
        cout << sa[i];
        if (i != n - 1) cout << " ";
    }
    cout << endl;
    
    // 输出Height数组
    for (int i = 0; i < n; i++) {
        cout << height[i];
        if (i != n - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}