#include "Anna.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int block_len = 112;
const int bits = 78;
namespace
{
int arr[100200];
__int128_t fib[block_len+1];
}
void Anna(int N, vector<char> S)
{
while(siz(S)%block_len != 0) S.pb('Y');
bool was = 0;
int n = siz(S);
rep(i,n) arr[i] = 0;
fib[0] = 1;
fib[1] = 2;
rep2(i,2,block_len) fib[i] = fib[i-1]+fib[i-2];
int fZ = -1;
for(int i = n-1; i >= 0; i--)
{
if(!was)
{
if(S[i] == 'Z')
{
was = 1;
arr[i] = 1;
i--;
fZ = i+1;
}
}
else if(S[i] == 'X')
{
if(i == 0 || S[i-1] != 'X')
{
arr[i] = 1;
}
}
}
rep(i,n/block_len)
{
__int128_t cur = 0;
rep2(j,i*block_len,(i+1)*block_len-1)
{
if(arr[j])
{
cur += fib[(i+1)*block_len-1-j];
}
}
rep(bit,bits)
{
if(cur & ((__int128_t)(1LL) << (__int128_t)bit)) Send(1);
else Send(0);
}
}
if(fZ >= 1 && S[fZ-1] == 'X') Send(1);
else Send(0);
}
#include "Bruno.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int block_len = 112;
const int bits = 78;
namespace {
__int128_t fib[block_len+1];
int arr[100200];
}
void Bruno(int n, int L, vi A)
{
int blocks = (n+block_len-1)/block_len;
fib[0] = 1;
fib[1] = 2;
rep2(i,2,block_len) fib[i] = fib[i-1]+fib[i-2];
rep(i,blocks)
{
__int128_t cur = 0;
int cnt = 0;
rep2(j,i*bits,(i+1)*bits-1)
{
cnt++;
if(A[j]) cur += ((__int128_t)(1) << (__int128_t)(j-i*bits));
}
rep(j,block_len)
{
if(cur < fib[block_len-1-j])
{
arr[i*block_len+j] = 0;
}
else
{
arr[i*block_len+j] = 1;
cur -= fib[block_len-1-j];
}
}
}
int pop = -1;
rep(i,n) if(arr[i] == 1) pop = i;
if(pop == -1)
{
rep(i,n) Remove(i);
return;
}
for(int i = pop+1; i < n; i++) Remove(i);
int beg = pop-1;
if(A.back() == 1)
{
Remove(pop-1);
pop--;
}
for(int i = beg; i >= 0; i--)
{
if(arr[i])
{
rep2(j,i+1,pop-1)
{
Remove(j);
}
Remove(i);
pop = i;
}
}
rep(j,pop) Remove(j);
Remove(beg+1);
}
