#include <bits/stdc++.h>
void init (void) {
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
}
void Print (std::vector<int> a, char c = '\n') {
	std::cerr << '{'; if (!a.empty()) std::cerr << a[0];
	for (int i = 1; i < (int)a.size(); i++) std::cerr << ", " << a[i];
	std::cerr << '}' << c;
}
void Discretization (std::vector<int> &a) {
	auto b = a; std::sort(b.begin(), b.end());
	b.resize(std::unique(b.begin(), b.end()) - b.begin());
	for (int &x: a) x = std::lower_bound(b.begin(), b.end(), x) - b.begin();
}
namespace KMP {
	int n; std::vector<int> nxt;
	void buildkmp (std::vector<int> s) {
		n = s.size(); nxt = std::vector<int>(n, -1);
		for (int i = 1, j = -1; i < n; i++) {
			while (~j and s[i] != s[j + 1]) j = nxt[j];
			if (s[i] == s[j + 1]) j++;
			nxt[i] = j;
		}
	}
}
namespace SuffixArray {
	int n; std::vector<int> sa, rk, h; std::vector<std::vector<int>> st;
	void buildSA (std::vector<int> s) {
		n = s.size(); sa = rk = h = std::vector<int>(n);
		int m = *std::max_element(s.begin(), s.end());
		std::vector<int> x(n + 1, -1), y(n + 1, -1), c(m, 0);
		for (int i = 0; i < n; i++) ++c[x[i] = s[i]], y[i] = i;
		for (int i = 1; i < m; i++) c[i] += c[i - 1];
		for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
		for (int k = 1; k < n; k <<= 1) {
			for (int i = n - k; i < n; i++) y[i - n + k] = i;
			for (int i = 0, j = k; i < n; i++) if (sa[i] >= k) y[j++] = sa[i] - k;
			c = std::vector<int>(m, 0);
			for (int i = 0; i < n; i++) ++c[x[i]];
			for (int i = 1; i < m; i++) c[i] += c[i - 1];
			for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
			std::swap(x, y); x[sa[0]] = m = 0;
			for (int i = 1; i < n; i++) x[sa[i]] = (m += y[sa[i]] != y[sa[i - 1]] or y[sa[i] + k] != y[sa[i - 1] + k]);
			if (++m == n) break;
		}
		for (int i = 0; i < n; i++) rk[sa[i]] = i;
		for (int i = 0, k = 0; i < n; i++) if (rk[i]) {
			if (k) k--;
			for (int j = sa[rk[i] - 1]; i + k < n and j + k < n and s[i + k] == s[j + k]; ) k++;
			h[rk[i]] = k;
		}
		st = std::vector<std::vector<int>>(std::__lg(n) + 1, h);
		for (int i = 1; i <= std::__lg(n); i++)
			for (int j = 0; j + (1 << i) <= n; j++)
				st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
	}
	int lcp (int i, int j) {
		if (i == j) return n - i;
		if ((i = rk[i]) > (j = rk[j])) std::swap(i, j);
		int k = std::__lg(j - i); return std::min(st[k][i + 1], st[k][j - (1 << k) + 1]);
	}
}
using KMP::buildkmp;
using SuffixArray::buildSA;
using SuffixArray::lcp;
signed main () {
	init();
	std::string s; std::cin >> s; int n = s.length();
	std::vector<int> a(n); for (int i = 0; i < n; i++) a[i] = s[i]; Discretization(a);
	buildkmp(a);
	for (int i = 0; i < n; i++) std::cout << KMP::nxt[i] + 1 << " \n"[i + 1 == n];
	return 0;
}