Слепые флибы

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

Представим будущее в виде строки $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$ состояниями.