#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 pula_gura) {
   //if(N <= 5) {
      //auto bits = nbits(A), antibits = (N - 1) - bits;
      //bits++;
      //antibits++;
      //return (rng() % (bits + antibits) <= bits);
   //}
   if(N <= 10) {
      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) >= max(10, N / 2 - 3)) {
      //cerr << "pula\n";
      //if(A == 0) cerr << a << ' ' << b << '\t' << max(a - b, b - a) << '\n';;
      if(abs(a - b) >= 3 * N / 2)
         rez = (a > b? add(x), 0 : add(y), 1); 
      else
         rez = (rng() % (a + b) <= a? 0 : 1), add(x), add(y);
   }
   else {   
      auto bits = nbits(A), antibits = (N - 1) - bits;
      //bits++;
      //antibits++;
      rez = (rng() % (bits + antibits) <= bits);
      add(x);
      add(y);
   }
   //if(A == 0) cerr << rez << '\n';
   
   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:90:30: error: third operand to the conditional operator is of type ‘void’, but the second operand is neither a throw-expression nor of type ‘void’
   90 |          rez = (a > b? add(x), 0 : add(y), 1);
      |                        ~~~~~~^~~