#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);
    }
};

unordered_map<ull, int, custom_hash> appeared;


int N;

ull minform(ull A) {
   ull B = A;
   for(int i = 0; i < N; i++) A = (A >> 1) | ((A & 1) << (N - 1)), B = min(B, A);
   return B;
}

void add(ull A) {
   appeared[A]++;
   return;
}

mt19937 rng;

void init (signed N_, bool Type, signed p) {
   N = N_;
   rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
   //c = (abc() % 1000) + 1000;
   //a = abc() % 950 + 23;
   //b = abc() % 950 + 23;
   //seed = abc() % 10000;
}


//int rng() {
   //seed = (seed * a + b) % c;
   //return seed;
//}


bool guess (unsigned long long A, signed x) {
   if(N <= 15) {
      return rng() % 2;
   }
   int rez = 0;
   int a = 0, b = 0;
   int x = minform(A << 1), y = minform(A << 1 | 1);
   if(appeared.count(x)) a = appeared[x];
   if(appeared.count(y)) b = appeared[y];
   if(max(b - a, a - b) >= 8) {
      //cerr << "pula\n";
      //if(A == 0) cerr << a << ' ' << b << '\t' << max(a - b, b - a) << '\n';;
      rez = (a > b? 0 : 1); 
   }
   else {   
      auto bits = nbits(A), antibits = (N - 1) - bits;
      bits++;
      antibits++;
      rez = (rng() % (bits + antibits) <= bits);
   }
   //if(A == 0) cerr << rez << '\n';
   
   add(x);
   add(y);
   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 guess(long long unsigned int, int)’:
answer.code:77:8: error: declaration of ‘int x’ shadows a parameter
   77 |    int x = minform(A << 1), y = minform(A << 1 | 1);
      |        ^
answer.code:71:42: note: ‘int x’ previously declared here
   71 | bool guess (unsigned long long A, signed x) {
      |                                   ~~~~~~~^