#include "Anna.h"

using namespace std;
using ull = unsigned long long;

const int kS = 63, kB = 44;

ull af[kS];
auto init_af = []() {
  af[0] = 1, af[1] = 2;
  for (int i = 2; i < kS; ++i) {
    af[i] = af[i - 1] + af[i - 2];
  }
  return 0;
}();

void Anna(int n, vector<char> s) {
  s.push_back('X');
  vector<int> v;
  int px = -1;
  for (int i = 0; i < n; ++i) {
    char c = s[i];
    if (~px) {
      v.push_back(c == 'Z' && i != px + 1 && s[i + 1] != 'Z');
    } else {
      v.push_back(c == 'X');
      px += (c == 'X') * (i + 1);
    }
  }
  for (; v.size() % kS; v.push_back(0)) {
  }
  Send(s[px + 1] == 'Z');
  for (int i = 0; i < n; i += kS) {
    ull fs = 0;
    for (int j = 0; j < kS; ++j) {
      fs += v[i + j] * af[kS - 1 - j];
    }
    for (int j = 0; j < kB; ++j) {
      Send(fs >> j & 1);
    }
  }
}

#include "Bruno.h"

using namespace std;
using ull = unsigned long long;

const int kS = 63, kB = 44;

ull bf[kS];
auto init_bf = []() {
  bf[0] = 1, bf[1] = 2;
  for (int i = 2; i < kS; ++i) {
    bf[i] = bf[i - 1] + bf[i - 2];
  }
  return 0;
}();

void remove(int n, int d) {
  if (d < n) {
    Remove(d);
  }
}
void Bruno(int n, int la, vector<int> a) {
  int px = -1;
  vector<int> s;
  for (int i = 1, ri = 0; i < la; i += kB, ri += kS) {
    ull fs = 0;
    for (int j = 0; j < kB; ++j) {
      fs |= (ull)a[i + j] << j;
    }
    for (int j = kS - 1; j >= 0; --j) {
      int rj = ri + kS - 1 - j;
      bool v = fs >= bf[j];
      fs -= v * bf[j];
      if (~px) {
        if (v || a[0] && rj == px + 1) {
          for (; s.size() > 1; remove(n, s.back()), s.pop_back()) {
          }
          remove(n, rj);
        } else {
          s.push_back(rj);
        }
      } else {
        if (v) {
          s.push_back(rj);
          px = rj;
        } else {
          remove(n, rj);
        }
      }
    }
  }
  for (int i : s) {
    remove(n, i);
  }
}