Покрытие строки

Будем говорить, что строка $\alpha$ покрывает строку $\beta$, если для каждой позиции строки $\beta$ найдется такое вхождение $\alpha$ в $\beta$ как подстроки, которое содержит эту позицию. Например, строка "aba" покрывает строку "abaabaababa", но не покрывает строку "baba". Очевидно, любая строка покрывает сама себя.

Задана строка $w$. Для каждого ее префикса $w[1..k]$ найдите самую короткую строку, которая покрывает этот префикс.

Входной файл содержит строку $w$, состоящую из строчных букв латинского алфавита. Длина строки $w$ не превышает $250\,000$.

Для каждого $k$ от 1 до длины $w$ выведите длину самой короткой строки, которая покрывает $w[1..k]$.