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

using ll = long long;
using ld = long double;

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

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

using ull = unsigned long long;

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_set<ull, custom_hash> appeared;


int N;

bool count(ull A, bool& rez) {
   int cnt[2] = {0, 0};
   for(int i = 0; i < 2; i++) {
      if(appeared.count(A)) { rez = (A & 1); return 1; }
      for(int i = 1; i < N; i++) {
         if(appeared.count(A ^ (1 << i))) { rez = (A & 1); return 1; }
      }
      A ^= 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) >= 1e5) 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, int 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));
   
   //cerr << bitset<6>(A) << ' ' << rez << '\n';
   
   return rez;
}

/**
      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:8:13: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
    8 | #define int ull
      |             ^~~
answer.code:11:18: note: in expansion of macro ‘int’
   11 | using pii = pair<int,int>;
      |                  ^~~
answer.code:8:13: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
    8 | #define int ull
      |             ^~~
answer.code:11:22: note: in expansion of macro ‘int’
   11 | using pii = pair<int,int>;
      |                      ^~~
answer.code:11:25: error: template argument 1 is invalid
   11 | using pii = pair<int,int>;
      |                         ^
answer.code:11:25: error: template argument 2 is invalid
answer.code:8:13: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
    8 | #define int ull
      |             ^~~
answer.code:12:19: note: in expansion of macro ‘int’
   12 | using tii = tuple<int,int,int>;
      |                   ^~~
answer.code:8:13: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
    8 | #define int ull
      |             ^~~
answer.code:12:23: note: in expansion of macro ‘int’
   12 | using tii = tuple<int,int,int>;
      |                       ^~~
answer.code:8:13: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
    8 | #define int ull
      |             ^~~
answer.code:12:27: note: in expansion of macro ‘int’
   12 | using tii = tuple<int,int,int>;
      |                           ^~~
answer.code:12:30: error: template argument 1 is invalid
   12 | using tii = tuple<int,int,int>;
      |                              ^
answer.code:12:30: error: template argument 2 is invalid
answer.code:12:30: error: template argument 3 is invalid