Boundary Spell
The great wizard Merlin is crafting a new spell to safeguard the borders of the Faraway Kingdom. To analyze the spell more thoroughly, Merlin has decided to determine its magical code and compare it with those recommended in wizardry books.
The spell is represented by a word w of length n, made up of magical runes, denoted by lowercase Latin letters. A spell is considered non-trivial if it has a non-empty prefix, distinct from the entire spell, that also serves as its suffix. For instance, the spell "abababa" is non-trivial because the prefix "ababa" is also a suffix, whereas the spell "aababab" is not non-trivial.
Merlin examines all cyclic shifts of the spell w from 1 to n, where the i-th cyclic shift begins with the i-th character of the original spell. For example, the first cyclic shift of the spell "abababa" is "abababa", the second is "bababaa", and so forth, with the seventh cyclic shift being "aababab".
The magical code of the spell w, denoted as B(w), is a sequence of n characters, each being either "0" or "1". The i-th character of B(w) is "1" if the i-th cyclic shift of w is non-trivial, and "0" if it is not. For example, the magical code for the spell "abababa" is "1011110".
Assist Merlin in determining the magical code of the given spell w.
Input
The input consists of the spell w, which is a string of lowercase Latin letters. Its length does not exceed 100,000.
Output
Output the magical code of the given spell.