Заклинание границы
Великий волшебник Мерлин разрабатывает новое заклинание для защиты границы Неблизкого королевства. Для более подробного анализа заклинания Мерлин решил выяснить магический код заклинания и сравнить его с рекомендуемыми в книгах по волшебству.
Заклинание представляет собой слово 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, состоящее из маленьких букв латинского алфавита. Его длина не превышает 100000.
Выходные данные
Выведите в выходной файл магический код заданного заклинания.