Подсчеты, где постоянно нужно брать остаток от деления на $998244353$ или $10^9+7$, использование FFT и многоточечной оценки — всё это уже порядком надоело.

Для задач с маленькими простыми модулями существует немало прецедентов, например, задача, которую zx2003 пытался объяснить в прошлом году: коэффициенты высоких степеней малых многочленов по модулю малого простого числа.

Сегодня мы не будем заниматься ничем подобным, будем работать по модулю $2$, так что давайте посмотрим на нули и единицы.

У вас есть множество натуральных чисел $S$. Вам нужно для каждого $1\le k\le n$ найти количество способов распределить шары с номерами от $1$ до $k$ по нескольким ящикам так, чтобы количество шаров в каждом ящике принадлежало $S$. Вас интересует только четность этого количества.

Примечание: шары различимы, ящики неразличимы.

Входные данные

На вход подается строка из $0$ и $1$ длиной $n$. Если $x$-й символ равен $1$, это означает, что $x\in S$.

Выходные данные

Выведите строку из $0$ и $1$ длиной $n$, где $k$-й символ обозначает $a_k \bmod 2$.

Примеры

Пример 1

Входные данные

10110

Выходные данные

11000

Примечание

Для примера $1$ приведем количество способов для каждого $k$:

$k=1$: $\{\{1\}\}$, всего $1$ способ.

$k=2$: $\{\{1\},\{2\}\}$, всего $1$ способ.

$k=3$: $\{\{1\},\{2\},\{3\}\},\{\{1,2,3\}\}$, всего $2$ способа.

$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\}\}$
• Всего $6$ способов.

$k=5$: всего $16$ способов, перечислять не будем.

Подзадачи

Для $10\%$ данных $n\le 10$.

Для $40\%$ данных $n\le 2000$.

Для $70\%$ данных $n\le 3\times 10^5$.

Для $100\%$ данных $n\le 2\times 10^6$.