Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.
Вычислить длины блоков строки S для всех позиций.
Единственная строка S (|S| ≤ 10^6
).
В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.