#! /usr/bin/env python
import sys
from poly import *

def LFSR(state, p):
	sum = 0
	for i in range(0, len(state)):
		sum = sum + (state[i] * p[-i-1])
	state = state[1:len(state)]
	state.append(sum % 2)
	return state
	
def BerlekampMassey(s):
	print s
	C, L, m, B, N = poly([1]), 0, -1, poly([1]), 0
	while (N < len(s)):
		d = reduce((lambda x, y: x + y),\
		map((lambda x, y: x * y), map((lambda x, c = C: c[x]), range(1, L + 1)),\
		map((lambda x, n = N, S = s: int(S[n - x])), range(1, L + 1))), (int(s[N]))) % 2
		if (d == 1):
			T, C = C.copy(), C ^ (B * spoly(N - m, 1))
			if (L <= (N / 2)):
				L, m, B = N + 1 - L, N, T
		N = N + 1
	return (L, C)

s = sys.stdin.read()
		
(L, C) = BerlekampMassey(s)
sys.stderr.write(str(L) + " " + str(C) + "\n")

st = []
for i in range(0, L):
	st.append(int(s[i]))
C.resize(L + 1)

if (L == 0):
	st.append(int(s[0]))

for i in range(0, len(s)):
	sys.stderr.write(str(st[0]))
	st = LFSR(st, C)
sys.stderr.write("\n")