#include "Anna.h"
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define vep(i,x) for(unsigned int i=0;i<x.size();++i)
#define mar(o) for(int E=fst[o];E;E=e[E].nxt)
#define v e[E].to
#define lon unsigned long long
using namespace std;
const int n7=101234;

	lon f[123];int is[n7];
	
	void Dfib(){
		f[0]=1,f[1]=2;
		rep(i,2,64){
			f[i]=f[i-1]+f[i-2];
		}
	}
	
	void Anna(int n,vector <char> a){
		int wei=-1;
		vep(i,a){
			if(a[i]=='X'){
				wei=i;
				rep(j,0,15)Send(i&1),i>>=1;
				break;				
			}
		}
		if(wei==-1){
			rep(j,0,15)Send(1);
			return;
		}
		rep(i,wei+1,n-1){
			if(a[i]=='Z'&&a[i+1]^'Z')is[i]=1;
		}
		Dfib();
		rep(i,wei+1,n-1){
			int l=i,r=min(n-1,i+64);lon x=0,tot=0;
			rep(j,l,r)if(is[j])x|=( 1ll<<(j-l) );
			per(j,64,0){
				if( x&(1ll<<j) )tot+=f[j];
			}
			rep(j,0,44)Send(tot&1),tot>>=1;
			i=r;
		}
	}

#include "Bruno.h"
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define vep(i,x) for(unsigned int i=0;i<x.size();++i)
#define mar(o) for(int E=fst[o];E;E=e[E].nxt)
#define v e[E].to
#define lon unsigned long long
using namespace std;
const int n7=101234;

	lon f[123];int b[n7];
	
	void Dfib(){
		f[0]=1,f[1]=2;
		rep(i,2,64){
			f[i]=f[i-1]+f[i-2];
		}
	}
	
	void Bruno(int n,int m,vector <int> a){
		bool flag=0;
		rep(i,0,15){
			flag|=(a[i]==0);
		}
		if(!flag){
			rep(i,0,n-1)Remove(i);
			return;
		}
		int wei=0;
		per(i,15,0){
			wei=(wei<<1)+a[i];
		}
		Dfib();
		rep(i,0,wei-1)Remove(i);
		int poi=wei;
		rep(i,16,m-1){
			int l=i,r=min(m-1,i+44);lon x=0,tot=0;
			per(j,r,l){
				tot=(tot<<1)+a[j];
			}
			per(j,64,0){
				if(tot>=f[j])x|=(1llu<<j),tot-=f[j];
			}
			int r2=min(n-1,poi+64);
			rep(j,poi,r2){
				if( x&( 1ll<<(j-poi) ) )b[j+1]=1;
			}
			i=r,poi=r2+1;
		}
		int l=wei+1;
		rep(i,wei,n-1){
			if(b[i]){
				per(j,i-1,l)Remove(j);
				Remove(i),l=i+1;
			}
		}
		rep(i,l,n-1)Remove(i);
		Remove(wei);
	}