Заклинание границы

Великий волшебник Мерлин разрабатывает новое заклинание для защиты границы Неблизкого королевства. Для более подробного анализа заклинания Мерлин решил выяснить магический код заклинания и сравнить его с рекомендуемыми в книгах по волшебству.

Заклинание представляет собой слово $w$ длины $n$, составленное из магических рун, которые мы обозначим маленькими буквами латинского алфавита. Будем говорить, что заклинание нетривиально, если у него есть непустой префикс, отличный от всего заклинания, который одновременно является его суффиксом. Например, заклинание <<abababa>> нетривиально, поскольку его префикс <<ababa>> также является его суффиксом, а заклинание <<aababab>> не является нетривиальным.

Мерлин рассматривает все циклические сдвиги заклинания $w$ от 1 до $n$, $i$-м считается циклический сдвиг, начинающийся с $i$-го символа исходного заклинания, например, первый циклический сдвиг заклинания <<abababa>> равен <<abababa>>, второй --- <<bababaa>>, и т. д., седьмой циклический сдвиг равен <<aababab>>.

Магический код заклинания $w$, который обозначается как $B(w)$, представляет собой слово, составленное из $n$ символов <<0>> и <<1>>. При этом $i$-й символ $B(w)$ равен <<1>>, если $i$-й циклический сдвиг $w$ нетривиален и <<0>>, если это не так. Например, магический код заклинания <<abababa>> равен <<1011110>>.

Помогите Мерлину по заданному заклинанию $w$ найти его магический код.

Входной файл содержит заклинание $w$, состоящее из маленьких букв латинского алфавита.ъ Его длина не превышает $100\\,000$.

Выведите в выходной файл магический код заданного заклинания.