Блоки строки

Блоком строки $S$ в позиции $i$ назовём наибольшую подстроку $S$, которая начинается в позиции $i$ и совпадает с ее префиксом. Длину блока в позиции $0$ будем считать равной нулю.

Вычислите длины блоков строки $S$ для всех позиций.

Входные данные

Одна строка $S(|S|\le 10^6)$.

Выходные данные

В одной строке выведите длины блоков строки $S$ для всех позиций.

Примеры