#include<bits/stdc++.h>
#include "Anna.h"
#define ll long long
using namespace std;
int Declare() { return 140; }
pair<vector<int>,vector<int>> Anna(ll A) {
	vector <ll> dp(140); dp[0]=dp[1]=1,dp[2]=2;
	for(int i=3;i<140;++i) dp[i]=dp[i-2]+dp[i-3]+1;
	int lst=1;
	ll DP=accumulate(dp.begin(),dp.end(),0ll);
	--A;
	if(A>DP) A-=DP,lst=0;
	vector <int> S{lst},T{lst};
	int k=0;
	while(A>=dp[k]) A-=dp[k++];
	for(int d=k;d;) {
		if(!A) {
			while((int)S.size()<=k) S.push_back(S.back()^1);
			break;
		}
		--A;
		int v=S.back();
		if(A>=dp[d-2]) {
			A-=dp[d-2],S.insert(S.end(),{v^1,v^1,v^1}),d-=3;
		} else {
			S.insert(S.end(),{v,v}),d-=2;
		}
	}
	while(T.size()<S.size()) T.push_back(T.back()^1);
	return {S,T};
}

#include<bits/stdc++.h>
#include "Bruno.h"
#define ll long long
using namespace std;
ll Bruno(vector<int> u) {
	vector <ll> dp(140); dp[0]=dp[1]=1,dp[2]=2;
	for(int i=3;i<140;++i) dp[i]=dp[i-2]+dp[i-3]+1;
	ll A=u[0]?0:accumulate(dp.begin(),dp.end(),0ll);
	int k=u.size()/2-1,s=0;
	for(int i=0;i<k;++i) A+=dp[i];
	int lst=u[0],d=k;
	for(int i=1;i<(int)u.size();++i) {
		s+=u[i]?1:-1;
		if(s==2||s==-2) {
			int tmp=(s==2); ++A;
			if(tmp==lst) d-=2;
			else A+=dp[d-2],d-=3;
			lst=tmp,s=0;
		}
	}
	return ++A;
}