#ifndef davele
#include "Anna.h"
#endif // davele
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;
//const int mod = ;
//void add (int &a, const int&b){
// a+=b;
// if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
// a-=b;
// if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
// a*=b;
// a%=mod;
//}
template<class X, class Y>
bool minimize(X &x, const Y&y){
if (x<=y) return false;
else{
x = y;
return true;
}
}
template<class X, class Y>
bool maximize (X &x, const Y&y){
if (x>=y) return false;
else{
x = y;
return true;
}
}
/////////////////////////////////////////////////////////////////////////////////
const int limit = 1e5+5, compressed_len = 43, ini_len = 63;
string s;
long long fib[1000];
int ans[limit];
void prep(){
fib[0] = 1;
fib[1] = 2;
fib[2] = 3;
for (int i=3; i<=91; i++) fib[i] = fib[i-1]+fib[i-2];
//
}
long long trans_to_int (int l, int r){
int len = r-l+1;
// for (int i=0; i<=len; i++) cerr<<i<<" "<<fib[i]<<"\n";
long long ranks = 1;
for (int i=l; i<=r; i++){
// cerr<<ans[i]<<" ";
len--;
if (ans[i]==1){
ranks+=fib[len];
}
}
// cerr<<"\n";
// cerr<<ranks<<"\n";
return ranks;
}
int curpos;
void Anna (int n, std::vector<char> S){
curpos = 0;
prep();
string s=" ";
for (char x:S) s+=x;
int last = n;
for (int i=0; i<=n; i++){
if (i!=n && s[i+1]=='X'){
ans[curpos++] = 1;
last = i;
break;
}
ans[curpos++] = 0;
}
if (last!=n){
for (int i=last+1; i<=n; i++){
if (s[i]=='Z'){
if (i==n || s[i+1]!='Z') ans[curpos++] = 1;
else ans[curpos++] = 0;
}
else ans[curpos++] = 0;
}
}
// for (int i=0; i<curpos; i++) cerr<<ans[i];
// cerr<<"\n";
for (int i=0; i<=n; i+=63){
long long tmp = trans_to_int (i, min(n, i+63-1));
for (int j=0; j<=43; j++) if (MASK(j)&tmp) Send(1);
else Send(0);
}
}
#ifndef davele
#include "Bruno.h"
#endif // davele
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;
//const int mod = ;
//void add (int &a, const int&b){
// a+=b;
// if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
// a-=b;
// if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
// a*=b;
// a%=mod;
//}
template<class X, class Y>
bool minimize(X &x, const Y&y){
if (x<=y) return false;
else{
x = y;
return true;
}
}
template<class X, class Y>
bool maximize (X &x, const Y&y){
if (x>=y) return false;
else{
x = y;
return true;
}
}
/////////////////////////////////////////////////////////////////////////////////
const int limit = 1e5+5, compressed_len = 44, ini_len = 63;
long long fib[1000];
int b[limit];
int N;
int len = 0;
void decode( long long val){
// cerr<<val<<"\n";
string tmp ="";
for (int i=63; i>=1; i--){
if (val>fib[i-1]){
tmp+="1";
val-=fib[i-1];
}
else tmp+="0";
}
// cerr<<tmp<<"\n";
if (len+62<=N){
for (char x:tmp) b[len++] = x-'0';
}
else{
int st = 63-(N-len)+1;
for (int i=st; i<=63; i++) b[len++] = tmp[i-1]-'0';
}
// for (int i=0; i<len; i++) cerr<<b[i];
// cerr<<"\n";
}
void prep(){
fib[0] = 1;
fib[1] = 2;
fib[2] = 3;
for (int i=3; i<=91; i++) fib[i] = fib[i-1]+fib[i-2];
//
}
void Bruno (int n, int l, std::vector<int> tmp){
N = n+1;
len = 0;
prep();
//
int numloop = l/44;
int curbit = 0;
//
for (int loop = 1; loop<=numloop; loop++){
long long encode_val = 0;
for (int i=0; i<=43; i++){
// cerr<<tmp[curbit];
encode_val += tmp[curbit]*MASK(i);
curbit++;
}
// cerr<<"\n";
decode(encode_val);
}
// cerr<<"ok";
//
bool have1 = false;
if (b[n]==1){
have1 = true;
}
for (int i = n; i>0; i--){
if (have1) break;
if (b[i-1]==1){
have1 = true;
break;
}
Remove(i-1);
}
if (!have1) return;
for (int i=0; i<n; i++){
if (b[i]==1){
break;
}
Remove(i);
}
vector <int> list1;
for (int i=0; i<=n; i++) if (b[i]==1){
list1.pb(i-1);
if (list1.size()==1) list1.back()++;
}
if (list1.size()>1 && list1.back()+1<n){
Remove (list1.back()+1);
}
for (int i=1; i<list1.size(); i++){
int st = list1[i-1]+1;
int en = list1[i]-1;
for (int j=en; j>=st; j--) Remove(j);
Remove(list1[i]);
}
Remove(list1[0]);
}
