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

Обчислити довжини блоків рядка S для усіх позицій.

Вхідні дані

Єдиний рядок S (|S| ≤ 106).

Вихідні дані

В одному рядку вивести довжини блоків рядку S для усіх позицій, розділених пропуском.