Boundary Spell

The great wizard Merlin is developing a new spell to protect the border of the Nearby Kingdom. To analyze the spell in more detail, Merlin wants to find its magic code and compare it with the codes recommended in the spellbooks.

The spell is a word $w$ of length $n$, made of magic runes written as lowercase Latin letters. A spell is called nontrivial if it has a nonempty prefix, different from the whole spell, that is also a suffix of it. For example, abababa is nontrivial because its prefix ababa is also its suffix. aababab is not nontrivial.

Merlin considers all cyclic shifts of $w$ from 1 to $n$. The $i$-th cyclic shift starts at the $i$-th character of the original spell. For example, the first cyclic shift of abababa is abababa, the second is bababaa, and the seventh is aababab.

The magic code of spell $w$, written $B(w)$, is a word of $n$ characters, each 0 or 1. The $i$-th character of $B(w)$ is 1 if the $i$-th cyclic shift of $w$ is nontrivial, and 0 otherwise. For example, the magic code of abababa is 1011110.

Given spell $w$, find its magic code.

The input file contains the spell $w$, consisting of lowercase Latin letters. Its length does not exceed 100,000.

Print the magic code of the given spell.