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

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for (int i=(a); i<(b); ++i)
typedef vector<int> vi;

struct SuffixArray {
	vi sa, lcp;
	SuffixArray(string &s, int lim = 256) {
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j=0, p=0; p<n; j=max(1,j*2), lim=p) {
			p = j, iota(all(y), n-j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i-1];
			for (int i=n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i-1], b = sa[i], x[b] = (y[a] == y[b] && y[a+j] == y[b+j]) ? p-1 : p++;
		}
		rep(i,1,n) rank[sa[i]] = i;
		for (int i=0, j; i<n-1; lcp[rank[i++]] = k)
			for (k && k--, j=sa[rank[i]-1]; s[i+k] == s[j+k]; k++);
	}
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s;
	cin >> s;
	int n = s.size();

	SuffixArray sa(s);

	for (int i=1; i<=n; i++) cout << sa.sa[i] << ' ';
	cout << '\n';
	for (int i=1; i<=n; i++) cout << sa.lcp[i] << ' ';
	cout << '\n';

	vector<int> par(n+1), sez(n+1), lb(n+1), rb(n+1), ans(n+1);
	vector<set<int>> vals(n+1);
	vector<map<int, int>> diffs(n+1);
	auto create = [&](int u) -> void {
		par[u] = lb[u] = rb[u] = u; sez[u] = 1; vals[u].insert(sa.sa[u]);
	};
	auto find = [&](auto self, int u) -> int {
		if (u != par[u]) return par[u] = self(self, par[u]);
		return u;
	};
	auto unite_set = [&](int u, int v) -> void {
		auto &val = vals[v];
		auto &diff = diffs[v];
		for (int x : vals[u]) {
			auto it = val.lower_bound(x);
			if (it != val.begin()) {
				auto prv = it;
				prv--;
				int y = *it - *prv;
				diff[y]--;
				if (diff[y] == 0) diff.erase(y);
			}

			val.insert(x);
			it = val.lower_bound(x);
			if (it != val.end()) {
				auto nxt = it;
				nxt++;
				if (nxt != val.end()) {
					int y = *nxt - x;
					diff[y]++;
				}
				if (it != val.begin()) {
					auto prv = it;
					prv--;
					int y = x - *prv;
					diff[y]++;
				}
			}
		}

		vals[u].clear();
		diffs[u].clear();
	};
	auto update_ans = [&](int u, int h) -> void {
		int len = rb[u] - lb[u] + 1;
		cout << lb[u] << ' ' << rb[u] << ' ' << len << ' ' << h+1 << ' ';
		cout << (diffs[u].empty() ? 1000 : diffs[u].begin()->first) << '\n';
		if (ans[len] == 0 && (diffs[u].empty() || diffs[u].begin()->first <= h+1)) ans[len] = h+1; 
	};
	auto unite = [&](int u, int v, int h) -> void {
		u = find(find, u); v = find(find, v);
		update_ans(u, h); update_ans(v, h);
		if (sez[u] > sez[v]) swap(u, v);
		par[u] = v; sez[v] += sez[u]; lb[v] = min(lb[u], lb[v]); rb[v] = max(rb[u], rb[v]);
		unite_set(u, v);
	};

	vector<int> pos(n);
	for (int i=1; i<=n; i++) pos[sa.sa[i]] = i;

	vector<int> idx(n+1);
	for (int i=0; i<=n; i++) idx[i] = i;
	sort(idx.begin()+1, idx.end(), [&](int i, int j) {
		return sa.lcp[i] > sa.lcp[j];
	});
	for (int h=n, i=1; h>0; h--) {
		create(pos[n - h]);
		while (i <= n && sa.lcp[idx[i]] >= h) {
			int j = idx[i];
			unite(j, j-1, h);
			i++;
		}
	}
	for (int i=1; i<=n; i++) {
		if (i == par[i]) update_ans(i, 0);
	}

	ans[1] = n;
	for (int i=1; i<=n; i++) cout << ans[i] << ' ';
	cout << '\n';

	return 0;
}