#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 200005;
char r,s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], n, rk[maxn], h[maxn]; //x一直是rank数组
void getSA(int m) { //0到m-1
int i, *x = t, *y = t2;
for (i = 0; i < m; ++i)c[i] = 0;
for (i = 0; i < n; ++i)x[i] = s[i];
for (i = 0; i < n; ++i)c[x[i]]++;
for (i = 1; i < m; ++i)c[i] += c[i - 1];
for (i = n - 1; i >= 0; --i)sa[--c[x[i]]] = i; //这是蓝书做法
for (int k = 1; k <= n; k <<= 1) {
int p = 0;
for (i = n - 1; i >= n - k; --i)y[p++] = i; //直接利用sa数组，第二关键字单个排序，y是由排名到下标的数组。
//这里要反排这样可以不用做最后一次排序，否则要再做一次
/*for (i = n - k; i < n; ++i)y[p++] = i;*/
for (i = 0; i < n; ++i)if (sa[i] >= k)y[p++] = sa[i] - k;
//基数排序求sa
for (i = 0; i < m; ++i)c[i] = 0;
for (i = 0; i < n; ++i)c[x[y[i]]]++;
for (i = 0; i < m; ++i)c[i] += c[i - 1];
for (i = n - 1; i >= 0; --i)sa[--c[x[y[i]]]] = y[i]; //第一次利用后缀位置优先序，这里利用第二关键字优先序
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (i = 1; i < n; ++i)
x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
if (p >= n)break;
m = p;
}
}
void getH() {
int i, j, k = 0;
for (i = 0; i < n; ++i)rk[sa[i]] = i;
for (i = 0; i < n; ++i) {
if (k)k--;
if (rk[i]) {
j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])k++;
}
h[rk[i]] = k;
}
}
int main() {
scanf("%s", s);
n = strlen(s);
for (int i = 0; i < n; ++i)s[i] = s[i] - 'a' + 1;
getSA(27);
getH();
if (n) {
for (int i = 0; i < n; ++i)printf("%d ", sa[i]+1); //默认序从0开始
printf("\n");
for (int i = 1; i < n; ++i)printf("%d ", h[i]);
}
return 0;
}