29612번 - Слепые флибы 스페셜 저지다국어

문제

Флибы --- фантастические существа, которые предсказывают будущее. Флибы часто используются при демонстрации использования генетических алгоритмов. В этой задаче мы исследуем свойства <<слепых>> флибов, которые пытаются предсказывать будущее, не получая никакой информации из окружающего мира.

Представим будущее в виде строки $w,ドル состоящей из нулей и единиц, приписанную к самой себе до бесконечности. В результате получается бесконечная строка $w^*$. Например, если $w = 010011,ドル будущее представляет собой строку $w^*=010011010011010011...$. Слепой флиб --- детерминированный конечный автомат, который выводит символ на каждом переходе.

Формально слепой флиб имеет $n$ состояний, из каждого состояния есть переход, помеченный 0 и переход, помеченный 1. Переход --- это тройка $\langle m, p, s \rangle,ドル где $m$ --- символ, которым помечен переход, $p$ --- символ, который выводится на переходе, а $s$ --- состояние, в которое флиб переходит, когда происходит этот переход.

Исходно флиб выводит некоторый символ (он может решить, какой) и переходит в состояние 1. После этого флиб действует следующим образом. Пусть $c$ --- последний символ, который вывел флиб. Он выбирает переход, помеченный символом $c,ドル и переходит по нему (выводя соответствующий этому переходу символ). Этот процесс продолжается до бесконечности.

Пусть $z$ --- бесконечная строка, выведенная флибом. Обозначим как $e(k)$ количество позиций среди первых $k,ドル на которых в строках $z$ и $w^*$ стоят одинаковые символы. При увеличении $k$ отношение $\frac{e(n)}{n}$ становится сколь угодно близко к некоторому числу $P$. Это число называется предсказательной способностью флиба. Чем выше предсказательная способность --- тем лучше флиб.

Например, очевидно, для любого $w$ существует слепой флиб с предсказательной способностью 1ドル.0$? содержащий $n$ состояний, где $n$ --- длина строка $w$. Состояние такого флиба соответствует позиции в строке $w,ドル до которой к текущему моменту она была выведена. Он всегда правильно предсказывает следующий символ.

Задано слово $w$. Для каждого $k$ от 1 до длины $w$ постройте слепого флиба с максимальной предсказательной способностью, имеющего $k$ состояний.

입력

Входной файл содержит слово $w$ (длина $w$ от 1 до 200, включительно, $w$ содержит только 0 и 1).

출력

Для всех $k$ от 1 до длины $w$ выведите максимальную возможную предсказательную способность слепого флиба с $k$ состояниями.

제한

힌트