#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]; bool test(int x){ return (W[x>>6]>>(x&63))&1; }void set(int x,bool v){ if(v) W[x>>6]|=1ull<<(x&63); else W[x>>6]&=((-1ull)-(1ull<<(x&63))); }int count(){ int res=0; rep(i,0,LEN){ res+=ppcl(W[i]); }return res; }int countx(int k){ int res=0; rep(i,0,(k>>6)-1){ res+=ppcl(W[i]); }res+=ppcl((ull)(W[k>>6]<<(63-(k&63)))); return res; }Bitset operator&(const Bitset &rh)const{ Bitset res; rep(i,0,LEN) res.W[i]=W[i]&rh.W[i]; return res; }Bitset operator|(const Bitset &rh)const{ Bitset res; rep(i,0,LEN) res.W[i]=W[i]|rh.W[i]; return res; }Bitset operator^(const Bitset &rh)const{ Bitset res; rep(i,0,LEN) res.W[i]=W[i]^rh.W[i]; return res; }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; } }void print(){ rep(i,0,2){ rep(j,0,63){ cout<<((W[i]>>j)&1); } }cout<<endl; } }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'); //bs.print(); //wg[0].print(); int now=0; for(int j=0;j<=pw;j++){ //now+=(wg[j]&bs).count(); now+=modify(wg[j],bs,i); //int dif=abs(((wg[j]&bs).count())-(modify(wg[j],bs,i))); //if(dif)cout<<i<<' '<<dif<<endl; //cout<<now<<' '; int id=now&1;now>>=1; if(id) f[i]|=1<<j; }//cout<<f[i]<<' '; 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++){ //Bitset x=wf[k]&wrf[j-k]; //now+=x.countx(cnt); 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); }//cout<<g[i]<<endl; } /*for(int i=1;i<=n;i++){ for(int j=0;j<=i;j++){ if(s[i-j]=='1') f[i]+=g[j]; } for(int j=0;j<i-j;j++){ g[i]+=f[j]*f[i-j]; } if(i%2==0) g[i]+=f[i/2]*(f[i/2]+1)/2; cout<<f[i]<<' '<<g[i]<<endl; }*/ for(int i=1;i<=n;i++){ cout<<f[i]%2; } pend