Блоки рядка

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

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

Вхідні дані

Єдиний рядок $S(|S|\le 10^6)$.

Вихідні дані

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

Приклади