#include<bits/stdc++.h> #define debug puts("SegTreeAKIOI") #define file freopen("modtwo.in","r",stdin),freopen("modtwo.out","w",stdout) #define pbegin int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pend cout.flush();return 0;} #define ll long long #define ull unsigned long long #define ui unsigned int #define i16 short #define ui16 unsigned short #define ppc __builtin_popcount #define ppcl __builtin_popcountll #define ctz __builtin_ctz #define ctzl __builtin_ctzll #define clz __builtin_clz #define clzl __builtin_clzll #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+11,mod=2,LEN=1565; struct Bitset{ ull W[(N>>6)+10]; void set(int x,bool v){ if(v) W[x>>6]|=1ull<<(x&63); else W[x>>6]&=((-1ull)-(1ull<<(x&63))); }void shift(int bcnt=LEN){ bool now=0,lst=0; rep(i,0,bcnt){ now=(W[i]>>63)&1; W[i]=(W[i]<<1)|lst; lst=now; } } }wf[23],wrf[23],wg[23],bs; ui f[N],g[N],n; string s; int modify(Bitset &a,Bitset &b,int cnt){ int bcnt=(cnt>>6)-1;cnt&=63; int res=0; rep(i,0,bcnt) res+=ppcl(a.W[i]&b.W[i]); res+=ppcl( (a.W[bcnt+1]&b.W[bcnt+1])& (ull)((2ull<<cnt)-1) ); return res; } pbegin file; cin>>s;n=s.length();s='0'+s; f[0]=1,g[0]=1; wf[0].set(0,1); wrf[0].set(0,1); wg[0].set(0,1); bs.set(0,0); int pw=20,val=0; for(int i=1;i<=n;i++){ pw=0,val=i; while(val*2<=n) pw++,val<<=1; bs.shift();bs.set(0,s[i]-'0'); int now=0; for(int j=0;j<=pw;j++){ now+=modify(wg[j],bs,i); int id=now&1;now>>=1; if(id) f[i]|=1<<j; } for(int j=0;j<=pw;j++){ wf[j].set(i,(f[i]>>j)&1); wrf[j].shift(i>>6); wrf[j].set(0,(f[i]>>j)&1); }int cnt=(i-1)/2;now=0; for(int j=0;j<=pw;j++){ for(int k=0;k<=j;k++){ now+=modify(wf[k],wrf[j-k],cnt); }int id=now&1;now>>=1; if(id) g[i]|=1<<j; }if(i%2==0) g[i]+=f[i/2]*(f[i/2]+1)/2; for(int j=0;j<=pw;j++){ wg[j].set(i,(g[i]>>j)&1); } } for(int i=1;i<=n;i++){ cout<<f[i]%2; } pend