Zliczanie rzeczy, ciągłe branie modulo $998244353$ czy $10^9+7$, odgrzewanie FFT i wielopunktowej ewaluacji wielomianów – to wszystko stało się już nudne.

Istnieje wiele precedensów dla problemów z małymi liczbami pierwszymi, jak na przykład próba pokazania przez zx2003 w zeszłym roku współczynników wysokich potęg małych wielomianów.

Dziś nie będziemy zajmować się niczym innym, tylko modulo $2$. Zatem przyjrzyjmy się zerom i jedynkom.

Masz dany zbiór liczb całkowitych dodatnich $S$. Odpowiedz dla każdego $1\le k\le n$, na ile sposobów można rozmieścić kule o numerach od $1$ do $k$ w pewnej liczbie pudełek tak, aby liczba kul w każdym pudełku należała do $S$. Interesuje Cię tylko parzystość wyniku.

Uwaga: kule są rozróżnialne, pudełka są nierozróżnialne.

Wejście

Wejście zawiera ciąg binarny o długości $n$. Jeśli $x$-ty znak jest równy $1$, oznacza to, że $x\in S$.

Wyjście

Wypisz ciąg binarny o długości $n$, w którym $k$-ty znak oznacza $a_k \bmod 2$.

Przykład

Przykład 1 Wejście

10110

Przykład 1 Wyjście

11000

Uwagi

Dla przykładu $1$, oto liczba sposobów dla każdego $k$:

$k=1$: $\{\{1\}\}$, łącznie $1$ sposób.

$k=2$: $\{\{1\},\{2\}\}$, łącznie $1$ sposób.

$k=3$: $\{\{1\},\{2\},\{3\}\},\{\{1,2,3\}\}$, łącznie $2$ sposoby.

$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\}\}$
• łącznie $6$ sposobów.

$k=5$: łącznie $16$ sposobów, nie będziemy ich wszystkich wymieniać.

Podzadania

Dla $10\%$ danych, $n\le 10$.

Dla $40\%$ danych, $n\le 2000$.

Dla $70\%$ danych, $n\le 3\times 10^5$.

Dla $100\%$ danych, $n\le 2\times 10^6$.