#include "nth.h"

/*
  F[L] + G[L] < C
  F[R] + G[R] >= C
  C = DA + DB + D
  (DA + ceil(D/2)-1) + (DB + ceil(D/2)-1) < C
  (DA + ceil(D/2)) + (DB + ceil(D/2)) >= C
*/

namespace Alice {
int L, R;
int DA, DB, D;

int F[M + 1];
bool a;
void go() {
  if (L + 1 == R) {
    exit(0);
  }
  sendA(a = (F[(L + R) >> 1] >= DA + (D + 1) / 2));
}

void initA(std::bitset<M> A, unsigned, unsigned C) {
  for (int x = 0; x < M; ++x) F[x + 1] = F[x] + A[x];
  L = 0; R = M;
  DA = 0; DB = 0; D = C;
  go();
}
void receiveA(bool b) {
  if (!a && !b) {
    L = (L + R) >> 1;
    go();
  } else if ((a && b) || D == 1) {
    R = (L + R) >> 1;
    go();
  } else {
    (a ? DA : DB) += D / 2;
    D -= D / 2;
    go();
  }
}
}  // Alice

////////////////////////////////////////////////////////////////////////////////

namespace Bob {
int L, R;
int DA, DB, D;

int G[M + 1];
bool b;
void go() {
  if (L + 1 == R) {
    report(L);
    exit(0);
  }
  sendB(b = (G[(L + R) >> 1] >= DB + (D + 1) / 2));
}

void initB(std::bitset<M> B, unsigned, unsigned C) {
  for (int x = 0; x < M; ++x) G[x + 1] = G[x] + B[x];
  L = 0; R = M;
  DA = 0; DB = 0; D = C;
  go();
}
void receiveB(bool a) {
  if (!a && !b) {
    L = (L + R) >> 1;
    go();
  } else if ((a && b) || D == 1) {
    R = (L + R) >> 1;
    go();
  } else {
    (a ? DA : DB) += D / 2;
    D -= D / 2;
    go();
  }
}
}  // Bob