Заданий непустий рядо \(S\) довжини \(N\) (\(1 \le N \le 10^6\))

Гранью (border) рядка назвемо найдовший суфікс (крім всього рядка) який співпадає з префіксом. Наприклад в рядку abceeabc грань буде abc (її довжина 3) В рядку abacaba грань буде aba (її довжина 3) В рядку abcd грань буде пустою (довжина 0) В рядку aaaaa грань буде aaaa (її довжина 4)

В заданому рядку знайдіть значення грані для кожного префікса заданого рядка

Формат вхідних даних

Рядок \(S\)

Формат вихідних даних

Виведіть через пробіл \(N\) чисел - значення префікс функції для кржної позиції

Приклад вхідних даних

abracadabra

Приклад вихідних даних

0 0 0 1 0 1 0 1 2 3 4

Пояснення

a - грань буде 0
ab - 0
abr - 0
abra - 1 (бо суффікс "a", дорівнює префіксу "a")
abrac - 0
abraca - 1 (бо суффікс "a", дорівнює префіксу "a")
abracad - 0
abracada - 1 (бо суффікс "a", дорівнює префіксу "a")
abracadab - 2 (бо суффікс "ab", дорівнює префіксу "ab")
abracadabr - 3 (бо суффікс "abr", дорівнює префіксу "abr") 
abracadabra - 4 (бо суффікс "abra", дорівнює префіксу "abra")