#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
#define sz(v) (int)v.size()
using bigint = vector<short>; //reversed order
const int base = 2;
bigint operator + (bigint a, bigint b){
int n = max(sz(a), sz(b));
a.resize(n);
b.resize(n);
bigint c(n);
int carry = 0;
for(int i = 0; i < n; ++i){
c[i] = a[i] + b[i] + carry;
if(c[i] >= base){
carry = 1;
c[i] -= base;
} else carry = 0;
}
if(carry) c.push_back(carry);
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
bool is_greater_or_equal(const bigint& a, const bigint& b){
if(sz(a) != sz(b)) return sz(a) > sz(b);
for(int i = sz(a)-1; i >= 0; --i){
if(a[i] != b[i]) return a[i] > b[i];
}
return true; //equal
}
bigint operator - (bigint a, bigint b){ //assume that a >= b
int n = max(sz(a), sz(b));
a.resize(n); b.resize(n);
int carry = 0;
bigint c(n);
for(int i = 0; i < n; ++i){
c[i] = a[i] - b[i] - carry;
if(c[i] < 0){
c[i] += base;
carry = 1;
} else carry = 0;
}
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
void show(const bigint& n){
if(n.empty()){
cout << 0 << '\n';
} else{
for(int i = sz(n)-1; i >= 0; --i) cout << n[i];
cout << '\n';
}
}
}
void Anna(int N, vector<char> S){
int f = -1;
for(int i = 0; i < N; ++i){
if(S[i] == 'X'){
f = i;
break;
}
}
if(f == -1){
Send(0);
return;
}
vector<bigint> fib(260);
fib[0] = {1};
fib[1] = {0, 1};
for(int i = 2; i < (int)fib.size(); ++i){
fib[i] = fib[i-2] + fib[i-1];
}
int nf = f;
while(nf + 1 < N && S[nf+1] == 'Z') ++nf;
vector<bool> bit(N);
bit[f] = true;
for(int i = nf + 1; i < N; ++i){
if(S[i] == 'Z') {
while(i+1 < N && S[i+1] == 'Z') ++i;
bit[i] = true;
}
}
const int T = 250;
const int B = 174;
for(int l = 0; l < N; l += T){
int r = min(N, l + T);
bigint sum = {};
for(int i = l; i < r; ++i){
if(bit[i]){
sum = sum + fib[i - l];
}
}
sum.resize(174);
for(int i = 0; i < B; ++i){
Send(sum[i]);
}
}
if(nf == f){
for(int i = 0; i < 17; ++i) Send(1);
} else{
for(int i = 0; i < 17; ++i) Send(nf >> i & 1);
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
namespace{
using bigint = vector<short>; //reversed order
const int base = 2;
bigint operator + (bigint a, bigint b){
int n = max(sz(a), sz(b));
a.resize(n);
b.resize(n);
bigint c(n);
int carry = 0;
for(int i = 0; i < n; ++i){
c[i] = a[i] + b[i] + carry;
if(c[i] >= base){
carry = 1;
c[i] -= base;
} else carry = 0;
}
if(carry) c.push_back(carry);
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
bool is_greater_or_equal(const bigint& a, const bigint& b){
if(sz(a) != sz(b)) return sz(a) > sz(b);
for(int i = sz(a)-1; i >= 0; --i){
if(a[i] != b[i]) return a[i] > b[i];
}
return true; //equal
}
bigint operator - (bigint a, bigint b){ //assume that a >= b
int n = max(sz(a), sz(b));
a.resize(n); b.resize(n);
int carry = 0;
bigint c(n);
for(int i = 0; i < n; ++i){
c[i] = a[i] - b[i] - carry;
if(c[i] < 0){
c[i] += base;
carry = 1;
} else carry = 0;
}
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
void show(const bigint& n){
if(n.empty()){
cout << 0 << '\n';
} else{
for(int i = sz(n)-1; i >= 0; --i) cout << n[i];
cout << '\n';
}
}
}
void Bruno(int N, int L, vector<int> A){
if(L == 1){
for(int i = 0; i < N; ++i) Remove(i);
return;
}
vector<bigint> fib(260);
fib[0] = {1};
fib[1] = {0, 1};
for(int i = 2; i < (int)fib.size(); ++i){
fib[i] = fib[i-2] + fib[i-1];
}
const int T = 250;
const int B = 174;
int nBlocks = L / B;
vector<bool> bit(N);
for(int b = 0; b < nBlocks; ++b){
int l = b * B, r = (b + 1) * B;
bigint sum = {};
for(int i = l; i < r; ++i){
sum.push_back(A[i]);
}
for(int i = T; i >= 0; --i){
if(is_greater_or_equal(sum, fib[i])){
sum = sum - fib[i];
bit[i + (b * T)] = 1;
}
}
}
int extra = 0;
for(int i = 0; i < 17; ++i){
if(A[i + nBlocks * B]) extra |= (1 << i);
}
int f = -1;
for(int i = 0; i < N; ++i){
if(bit[i]){
f = i;
break;
}
}
int s = -1;
for(int i = N - 1; i >= 0; --i){
if(bit[i]){
s = i;
break;
}
}
vector<int> result;
for(int i = 0; i < f; ++i) result.push_back(i);
for(int i = N-1; i > s; --i) result.push_back(i);
int old = -1;
if(extra < N){
old = f;
f = extra;
for(int i = old + 1; i <= f; ++i) result.push_back(i);
}
int last = f;
for(int i = f + 1; i <= s; ++i){
if(bit[i]){
for(int j = i-1; j > last; --j) result.push_back(j);
result.push_back(i);
last = i;
}
}
if(old != -1) result.push_back(old);
else result.push_back(f);
for(int i = 0; i < N; ++i) Remove(result[i]);
}
