Bit Sequence Renaming

King Byteasar of Bitotia has decreed a reformation of his subjects' names. In Bitotia the names may contain repeating phrases; for example, the name Abiabuabiab contains two occurrences of the phrase abiab. The king’s idea is to change every subject’s name into a bit sequence (i.e. a sequence of 0’s and 1’s) whose length equals the length of the original name while exactly preserving its set of periods.

For a sequence \(A = a_0a_1\ldots a_{n-1}\) (where the characters may be letters or bits) we say that an integer \(p, 1 \le p \le n\), is a period of \(A\) if for all indices \(i\) with \(0 \le i < n-p\) it holds that \(a_i = a_{i+p}\). (Note that when \(p=n\) the condition holds vacuously.) We denote the set of all periods of \(A\) by \(P(A)\).

For example, if the original name is ABIABUABIAB then its new name should be 01001101001, if the name is BABBAB then in the new naming it becomes 010010, and BABURBAB should be changed to 01000010.

Your task is to write a program that, given a name \(S\) (a sequence of letters considered case–insensitively), computes the lexicographically smallest bit sequence \(X\) (of length \(|S|\)) such that the set of periods of \(X\) is exactly \(P(S)\). In other words, for every \(p\) with \(1 \le p < |S|\) we require that:

• If \(p \in P(S)\) then \(x_i = x_{i+p}\) for all \(0 \le i < |S|-p\);
• If \(p \notin P(S)\) then there exists an index \(i, 0 \le i < |S|-p\), for which \(x_i \neq x_{i+p}\).

Input example:

ABIABUABIAB

Output example:

01001101001

If you succeed in implementing this translation, you may keep your current name as a reward!

inputFormat

The input consists of a single line containing a non–empty string \(S\) (its letters are to be regarded case–insensitively). The length of \(S\) is \(n\); note that the new name must be a bit sequence of length \(n\).

outputFormat

Output the lexicographically smallest bit sequence of length \(n\) whose set of periods is exactly \(P(S)\). (Recall that the lexicographic order is the usual order over binary sequences where 0 is considered less than 1.)

sample

ABIABUABIAB

01001101001