Counting things and taking modulo $998244353$ or $10^9+7$ all the time, along with FFTs and multi-point evaluation, is something everyone is tired of.

For problems involving small prime moduli, there are many precedents, such as the problem of coefficients of high-order powers of small polynomials at distant positions that zx2003 tried to teach everyone last year.

Today, we won't do anything else, just modulo $2$. So, let's look at zeros and ones.

You are given a set of positive integers $S$. For each $1\le k\le n$, please determine how many ways there are to place balls labeled $1$ to $k$ into some boxes such that the number of balls in each box belongs to $S$. You only want to know the parity of the answer.

Note: The balls are distinct, and the boxes are identical.

Input

The input is a binary string of length $n$, where the $x$-th character is $1$ if $x\in S$.

Output

Output a binary string of length $n$, where the $k$-th character represents $a_k \bmod 2$.

Examples

Input 1

10110

Output 1

11000

Note 1

For Example 1, the number of ways for each $k$ is:

$k=1$: $\{\{1\}\}$, total $1$ way.

$k=2$: $\{\{1\},\{2\}\}$, total $1$ way.

$k=3$: $\{\{1\},\{2\},\{3\}\},\{\{1,2,3\}\}$, total $2$ ways.

$k=4$:

• $\{\{1\},\{2\},\{3\},\{4\}\}$
• $\{\{1,2,3\},\{4\}\}$
• $\{\{1,2,4\},\{3\}\}$
• $\{\{1,3,4\},\{2\}\}$
• $\{\{1\}\{2,3,4\}\}$
• $\{\{1,2,3,4\}\}$
• Total $6$ ways.

$k=5$: Total $16$ ways, not listed individually.

Subtasks

For $10\%$ of the data, $n\le 10$.

For $40\%$ of the data, $n\le 2000$.

For $70\%$ of the data, $n\le 3\times 10^5$.

For $100\%$ of the data, $n\le 2\times 10^6$.