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

Заклинання являє собою слово 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.

Вихідні дані

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