Великий волшебник Мерлин разрабатывает новое заклинание для защиты границы Неблизкого королевства. Для более подробного анализа заклинания Мерлин решил выяснить магический код заклинания и сравнить его с рекомендуемыми в книгах по волшебству. Заклинание представляет собой слово \textbf{w} длины \textbf{n}, составленное из магических рун, которые мы обозначим маленькими буквами латинского алфавита. Будем говорить, что заклинание \textit{нетривиально}, если у него есть непустой префикс, отличный от всего заклинания, который одновременно является его суффиксом. Например, заклинание "\textbf{abababa}" нетривиально, поскольку его префикс "\textbf{ababa}" также является его суффиксом, а заклинание "\textbf{aababab}" не является нетривиальным. Мерлин рассматривает все циклические сдвиги заклинания \textbf{w} от \textbf{1} до \textbf{n}, \textbf{i}-м считается циклический сдвиг, начинающийся с \textbf{i}-го символа исходного заклинания, например, первый циклический сдвиг заклинания "\textbf{abababa}" равен "\textbf{abababa}", второй - "\textbf{bababaa}", и т. д., седьмой циклический сдвиг равен "\textbf{aababab}". Магический код заклинания \textbf{w}, который обозначается как \textbf{B(w)}, представляет собой слово, составленное из \textbf{n} символов "\textbf{0}" и "\textbf{1}". При этом \textbf{i}-й символ \textbf{B(w)} равен "\textbf{1}", если \textbf{i}-й циклический сдвиг \textbf{w} нетривиален и "\textbf{0}", если это не так. Например, магический код заклинания "\textbf{abababa}" равен "\textbf{1011110}". Помогите Мерлину по заданному заклинанию \textbf{w} найти его магический код. \InputFile Входной файл содержит заклинание \textbf{w}, состоящее из маленьких букв латинского алфавита. Его длина не превышает \textbf{100000}. \OutputFile Выведите в выходной файл магический код заданного заклинания.