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