#include "Anna.h"
#include <utility>
#include <vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
namespace {

ll dp[1005][2];
int n;
vector<int> solve(int x,int fl,ll nw)
{
	vector<int> ans;
	//printf("solve:x=%d,fl=%d,nw=%lld\n",x,fl,nw);
	if(x==1&&fl==1)
	{
		ans.push_back(1);
		return ans;
	}
	if(dp[x-2][fl]>=nw)
	{
		ans=solve(x-2,fl,nw);
		ans.push_back(fl);
		ans.push_back(fl);
		return ans;
	}
	nw-=dp[x-2][fl];
	ans=solve(x-3,fl^1,nw);
	ans.push_back(fl);
	ans.push_back(fl);
	ans.push_back(fl);
	return ans;
}
}

int Declare() {
	dp[1][1]=1;
	for(int i=1;;i++)
	{
		if(i>=3)
		{
			dp[i][0]=dp[i-2][0]+dp[i-3][1];
			dp[i][1]=dp[i-2][1]+dp[i-3][0];
		}
		ll sum=0;
		for(int j=1;j<=i;j++)
			sum+=(dp[j][0]+dp[j][1])*(i-j+1);
	//	printf("i=%d,dp=%lld,%lld,sum=%lld\n",i,dp[i][0],dp[i][1],sum);
		if(sum>5e17)
		{
			n=i;
			return n;
		}
	}
}

std::pair<std::vector<int>, std::vector<int> > Anna(long long A)
{
	ll nw=(A+1)/2;
	int fl=A%2;
//	printf("Anna\n");
	vector<int> ans1,ans2;
	for(int i=1;i<=n;i++)
	{
		if(nw<=dp[i][0]*(n-i+1))
		{
			int u=(nw-1)/dp[i][0];
			ans1=solve(i,0,(nw-1)%dp[i][0]+1);
			for(int i=1;i<=u;i++)
				ans1.push_back(i%2);
			break;
		}
		nw-=dp[i][0]*(n-i+1);
		if(nw<=dp[i][1]*(n-i+1))
		{
			int u=(nw-1)/dp[i][1];
			ans1=solve(i,1,(nw-1)%dp[i][1]+1);
			for(int i=1;i<=u;i++)
				ans1.push_back((i+1)%2);
			break;
		}
		nw-=dp[i][1]*(n-i+1);
	}
//	printf("Anna\n");
	int sz=ans1.size();
	for(int i=1;i<=sz;i++)
		ans2.push_back(i%2);
/*	printf("ans1=");
	for(int i=0;i<(int)ans1.size();i++)
		printf("%d ",ans1[i]);
	printf("\n");
	printf("ans2=");
	for(int i=0;i<(int)ans2.size();i++)
		printf("%d ",ans2[i]);
	printf("\n");*/
	if(fl)
	{
		for(int i=0;i<sz;i++)
			ans1[i]=1-ans1[i];
		for(int i=0;i<sz;i++)
			ans2[i]=1-ans2[i];
	}
	return make_pair(ans1,ans2);
}

#include "Bruno.h"
#include <utility>
#include <vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
namespace {

ll dp[1005][2];
int n;
void build() {
	dp[1][1]=1;
	for(int i=1;;i++)
	{
		if(i>=3)
		{
			dp[i][0]=dp[i-2][0]+dp[i-3][1];
			dp[i][1]=dp[i-2][1]+dp[i-3][0];
		}
		ll sum=0;
		for(int j=1;j<=i;j++)
			sum+=(dp[j][0]+dp[j][1])*(i-j+1);
	//	printf("i=%d,dp=%lld,%lld,sum=%lld\n",i,dp[i][0],dp[i][1],sum);
		if(sum>5e17)
		{
			n=i;
			return;
		}
	}
}
ll solve(vector<int> ans)
{
	int len=ans.size()-1;
	if(len==1) return 1;
	int fl=ans[len];
	if(len==3||ans[len-3]==fl)
	{
		ans.pop_back();
		ans.pop_back();
		return solve(ans);
	}
	ans.pop_back();
	ans.pop_back();
	ans.pop_back();
	return solve(ans)+dp[len-2][fl];
}
}

long long Bruno(std::vector<int> u)
{
	if(!n) build();
	int sum=-1,las=1,sz=u.size(),fl=0;
	if(!u[0])
	{
		for(int i=0;i<sz;i++)
			u[i]=1-u[i];
		fl=1;
	}
	vector<int> ans;
	ans.push_back(0);
	ans.push_back(1);
	for(int i=0;i<sz;i++)
	{
		sum+=u[i]*2-1;
	//	printf("i=%d,u=%d,sum=%d\n",i,u[i],sum);
		if(sum==2)
		{
			if(las==1)
			{
				ans.push_back(1);
				ans.push_back(1);
				sum=0;
			}
			else
			{
				ans.push_back(1);
				ans.push_back(1);
				ans.push_back(1);
				sum=0;
			}
			las=1;
		}
		if(sum==-2)
		{
			if(las==0)
			{
				ans.push_back(0);
				ans.push_back(0);
				sum=0;
			}
			else
			{
				ans.push_back(0);
				ans.push_back(0);
				ans.push_back(0);
				sum=0;
			}
			las=0;
		}
	}
	int len=ans.size()-1;
	ll nw=0;
	for(int i=1;i<len;i++)
		nw+=(dp[i][0]+dp[i][1])*(n-i+1);
	if(ans[len]==1) nw+=dp[len][0]*(n-len+1);
/*	printf("nw=%lld,solve=%lld,ans=",nw,solve(ans));
	for(int i=1;i<=len;i++)
		printf("%d ",ans[i]);
	printf("\n");*/
	return (nw+solve(ans)+dp[len][ans[len]]*(sz/2-len))*2-fl;
}