#include "Anna.h"
#include <bits/stdc++.h>

namespace {

constexpr int LG = 63;
constexpr int SZ = 44;
std::vector<std::array<int64_t, 2>> dp;
void init() {
  dp.resize(LG + 1);
  dp[1][0] = 1;
  dp[1][1] = 1;
  for (int i = 2; i <= LG; ++i) {
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
    dp[i][1] = dp[i - 1][0];
  }
}

} // namespace

void Anna(int N, std::vector<char> S) {
  const int n = N;
  std::string s(S.begin(), S.end());
  init();
  s.resize((n + LG - 1) / LG * LG, 'W');
  int st = -1;
  bool b = false;
  for (int i = 0; i < std::ssize(s); i += LG) {
    int64_t val = 0;
    for (int j = 0; j < LG; ++j) {
      if (s[i + j] == 'X' && st == -1) {
        val |= int64_t{1} << j;
        st = i + j;
      } else if (st != -1 && s[i + j] == 'Z' &&
                 (i + j == std::ssize(s) - 1 || s[i + j + 1] != 'Z')) {
        if (st == i + j - 1) {
          b = true;
        } else {
          val |= int64_t{1} << j;
        }
      }
    }
    int64_t num = 0;
    for (int j = LG - 1; j >= 0; --j) {
      if (((int64_t{1} << j) & val) != 0) {
        num += dp[j + 1][0];
      }
    }
    std::cerr << std::bitset<6>(val) << '\n';
    for (int j = 0; j < SZ; ++j) {
      Send(((int64_t{1} << j) & num) != 0 ? 1 : 0);
    }
  }
  Send(b ? 1 : 0);
}

#include "Bruno.h"
#include <bits/stdc++.h>

namespace {

constexpr int LG = 63;
constexpr int SZ = 44;
std::vector<std::array<int64_t, 2>> dp;
void init() {
  dp.resize(LG + 1);
  dp[1][0] = 1;
  dp[1][1] = 1;
  for (int i = 2; i <= LG; ++i) {
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
    dp[i][1] = dp[i - 1][0];
  }
}

} // namespace

void Bruno(int N, int L, std::vector<int> A) {
  const int n = N;
  const int l = L - 1;
  const std::vector<int> a = std::move(A);
  init();
  std::vector<bool> res(n);
  for (int i = 0; i < l; i += SZ) {
    int64_t num = 0;
    for (int j = 0; j < SZ; ++j) {
      if (a[i + j] == 1) {
        num |= int64_t{1} << j;
      }
    }
    int64_t val = 0;
    for (int j = LG - 1; j >= 0; --j) {
      if (num >= dp[j + 1][0]) {
        val |= int64_t{1} << j;
        num -= dp[j + 1][0];
      }
    }
    for (int j = 0; j < LG; ++j) {
      if (((int64_t{1} << j) & val) != 0) {
        res[(i / SZ) * LG + j] = true;
      }
    }
  }
  int st =
      static_cast<int>(std::find(res.begin(), res.end(), true) - res.begin());
  for (int i = 0; i < st; ++i) {
    Remove(i);
  }
  if (st == n) {
    return;
  }
  if (a[l] == 1) {
    res[st + 1] = true;
  }
  int orig = st;
  while (true) {
    int fi = static_cast<int>(std::find(res.begin() + st + 1, res.end(), true) -
                              res.begin());
    for (int j = fi - 1; j > st; --j) {
      Remove(j);
    }
    if (fi == n) {
      break;
    }
    Remove(fi);
    st = fi;
  }
  Remove(orig);
}