#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define int ull
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;


mt19937 rng(100);

int nbits(unsigned long long a) {
   if(a == 0) return 0;
   return 1 + nbits(a & (a - 1));
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

set<ull> appeared;


int N;

bool count(ull A, bool& rez) {
   int cnt[2] = {0, 0};
   for(int a = 0; a < 2; a++) {
      if(appeared.count(A)) { cnt[a]++; }
      for(int i = 1; i < N; i++) {
         if(appeared.count(A ^ (1 << i))) { cnt[a]++ }
      }
      A ^= 1;
   }
   
   if(cnt[0] + cnt[1] >= 5) {
      rez = (A & 1) ^ (rng() % (cnt[0] + cnt[1]) <= cnt[0]? 0 : 1);
      return 1;
   }
   
   
   return 0;
}

void add(ull A) {
   for(int i = 0; i < N; i++) {
      appeared.emplace(A);
      A = (A >> 1) | ((A & 1) << (N - 1));
   }
   if(sz(appeared) >= 1e4) appeared.clear();
   return;
}

void init (signed N_, bool Type, signed p) {
   N = N_;
   rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
   rng = mt19937(rng() % (10018421) * N + p);
}

bool guess (unsigned long long A, signed x) {
   auto bits = nbits(A), antibits = (N - 1) - bits;
   bool rez;
   
   auto a = rng() % (bits + antibits + 2) <= bits + 1;
   
   if(count((A << 1) | a, rez));
   else rez = rng() % (bits + antibits + 2) <= bits + 1;
   
   add((A << 1) | ((int)rez));
   
   return rez;
}
#undef int 

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

implementer.cpp: In function ‘int _JFIBEIIYTAFEUXOULOWO_::main()’:
implementer.cpp:18:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |         scanf("%d%d%d%d",&N,&Type,&p,&T);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
implementer.cpp:23:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   23 |                 scanf("%llu",&x);
      |                 ~~~~~^~~~~~~~~~~
answer.code: In function ‘bool count(ull, bool&)’:
answer.code:47:53: error: expected ‘;’ before ‘}’ token
   47 |          if(appeared.count(A ^ (1 << i))) { cnt[a]++ }
      |                                                     ^~
      |                                                     ;