#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Anna_solver{
struct Bignum{
vector<unsigned long long> val;
Bignum operator+(const Bignum &_) const {
auto a=val, b=_.val;
Bignum c;
c.val.resize(max(a.size(), b.size()));
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
unsigned long long carry=0, new_carry=0;
for (int i=0; i<(int)c.val.size(); ++i){
unsigned long long A=i<(int)a.size()?a[i]:0;
unsigned long long B=i<(int)b.size()?b[i]:0;
if (A>ULLONG_MAX-B || (A==ULLONG_MAX-B && carry)) new_carry=1;
else new_carry=0;
c.val[i]=A+B+carry;
carry=new_carry;
}
if (carry) c.val.push_back(1);
reverse(c.val.begin(), c.val.end());
return c;
}
};
const int M=1e5+10;
// Bignum fib[M];
void solve(int N, vector<char> S){
// fib[0].val={1};
// fib[1].val={2};
// for (int i=2; i<M; ++i){
// fib[i]=fib[i-1]+fib[i-2];
// }
int i=0;
while (i<N && S[i]!='X') ++i;
vector<int> v(N);
Bignum sum;
if (i<N){
v[i]=1;
for (int j=i; j<N; ++j) if (S[j]=='Z'){
int k=j;
while (k+1<N && S[k+1]=='Z') ++k;
v[k]=1;
j=k;
}
}
// for (int i=0; i<N; ++i) if (v[i]) sum=sum+fib[i];
Bignum a, b;
a.val={1}, b.val={2};
if (v[0]) sum=sum+a;
if (v[1]) sum=sum+b;
for (int i=2; i<N; ++i){
tie(a, b)=make_pair(b, a+b);
if (v[i]) sum=sum+b;
}
for (int i=0; i<(int)sum.val.size(); ++i){
for (int t=63; t>=0; --t) Send(sum.val[i]>>t&1);
}
}
}
void Anna(int N, std::vector<char> S) {
Anna_solver::solve(N, S);
}
#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Bruno_solver{
struct Bignum{
vector<unsigned long long> val;
Bignum operator+(const Bignum &_) const {
auto a=val, b=_.val;
Bignum c;
c.val.resize(max(a.size(), b.size()));
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
unsigned long long carry=0, new_carry=0;
for (int i=0; i<(int)c.val.size(); ++i){
unsigned long long A=i<(int)a.size()?a[i]:0;
unsigned long long B=i<(int)b.size()?b[i]:0;
if (A>ULLONG_MAX-B || (A==ULLONG_MAX-B && carry)) new_carry=1;
else new_carry=0;
c.val[i]=A+B+carry;
carry=new_carry;
}
if (carry) c.val.push_back(1);
reverse(c.val.begin(), c.val.end());
return c;
}
Bignum operator-(const Bignum &_) const {
auto a=val, b=_.val;
Bignum c;
c.val.resize(max(a.size(), b.size()));
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
unsigned long long carry=0, new_carry=0;
for (int i=0; i<(int)c.val.size(); ++i){
unsigned long long A=i<(int)a.size()?a[i]:0;
unsigned long long B=i<(int)b.size()?b[i]:0;
if (A<B || (A==B && carry)) new_carry=1;
else new_carry=0;
c.val[i]=A-B-carry;
carry=new_carry;
}
assert(!carry);
while (c.val.back()==0 && (int)c.val.size()>1) c.val.pop_back();
reverse(c.val.begin(), c.val.end());
return c;
}
bool operator>=(const Bignum &a) const {
if (val.size()!=a.val.size()) return val.size()>a.val.size();
for (int i=0; i<(int)val.size(); ++i) if (val[i]!=a.val[i]) return val[i]>a.val[i];
return 1;
}
};
const int M=1e5+10;
Bignum fib[M];
void solve(int N, int L, vector<int> B){
if (B.empty()){
for (int i=0; i<N; ++i) Remove(i);
return;
}
vector<int> A(N);
Bignum sum;
while ((int)B.size()%64) B.insert(B.begin(), 0);
for (int l=0, r=63; r<B.size(); l+=64, r+=64){
sum.val.emplace_back();
for (int j=l; j<=r; ++j) sum.val.back()=sum.val.back()<<1|B[j];
}
Bignum a, b;
a.val={1}; b.val={2};
for (int i=2; i<N; ++i){
tie(a, b)=make_pair(b, a+b);
}
for (int i=N-1; i>=0; --i){
if (sum>=b){
sum=sum-b;
A[i]=1;
}
tie(a, b)=make_pair(b-a, a);
}
int x=find(A.begin(), A.end(), 1)-A.begin();
for (int i=0; i<x; ++i) Remove(i);
int j=x+1;
for (int i=x+1; i<N; ++i) if (A[i]==1){
for (int k=i-1; k>=j; --k) Remove(k);
Remove(i);
j=i+1;
}
for (int i=j; i<N; ++i) Remove(i);
Remove(x);
}
} // namespace
void Bruno(int N, int L, std::vector<int> A) {
Bruno_solver::solve(N, L, A);
}
