#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <random>
#include <cmath>
#include <chrono>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <climits>
#include <stack>
#include <valarray>
#include <random>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define trav(a, x) for(auto& a : x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;
template<typename T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b){return b>a?a=b,1:0;}


template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(char c) {
  return string(1, c);
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


// #include <atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353; // modint1000000007;
// typedef vector<mint> vmi;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use rng() to get unsigned int
// mt19937_64 for random long longs

const int wyk = 5;
const int DL = (1 << wyk);
const int M = 1e7 + DL + 1;
int MAX_WYKLADNIK = 48;
int cnt[M];
int dz[M];
map<ll, int> maper;

#include "dzilib.h"

ll div_count(ll x) {
  if (maper.count(x)) {
    return maper[x];
  }
  return maper[x] = Ask(x);
}

void prep() {
  cnt[1] = 1;
  rep(i, 2, M) {
    if (i * i >= M) {
      break;
    }
    if (dz[i] == 0) {
      for (int j = i * i; j < M; j += i) {
        dz[j] = i;
      }
    }
  }
  rep(i, 2, M) {
    if (dz[i] == 0) cnt[i] = 2;
    else {
      int j = dz[i];
      int q = i, wyk = 0;
      while (q % j == 0) {
        q /= j;
        ++wyk;
      }
      cnt[i] = (wyk + 1) * cnt[q];
    }
  }
}

vi p;
int m;
int lps[DL + 1];

void preprocess() {
  m = sz(p);
  lps[0] = 0;
  int j = 0;
  for (int i=1; i<m; i++) {
    while (j != 0 && p[i] != p[j])
      j = lps[j-1]; 
    lps[i] = (j += (p[i] == p[j]));
  }
}

int kmp() {
    preprocess();
    vector<int> ret;
    int j = 0;
    // debug("kmp", p);
    for (int i=1; i < M; i++) {
        while (j != 0 && cnt[i] != p[j])
            j = lps[j-1];
        if ((j += (cnt[i] == p[j])) == m) {
          return i - j + 1;
        }
    }
    return -1;
}

vi conditions() {
  vi ans(DL);

  ans[0] = wyk + 1;
  ford(i, wyk, 0) {
    int val = (1 << i);
    for (int j = val; j < DL; j += val) {
      if (ans[j]) continue;
      ans[j] = i + 1;
    }
  }
  ans[0] = 0;

  return ans;
}

vi think(vector<int>::iterator p) {
  vi ok(DL);
  vi divs(DL);
  for (int i=0; i < DL; ++i, ++p) {
    divs[i] = *p;
  }
  vi conds = conditions();
  int kt = -1;
  set<int> interesting = {};
  vi ans;
  rep(i, 0, DL) {
    // debug("i", i);
    // can this number be | by 2^5
    // must be divisible by at least 6
    // number +- 2^4 must be divisible by at least 5
    // number
    // cout << "FOR SHIFT: " << i << endl;
    // rep(idx, 1, sz(conds)) {
    //   if (conds[idx] == 0) continue;
    //   cout << (i + idx) % DL << ": " << divs[(i + idx) % DL] / conds[idx] << endl;
    // }
    if (divs[i] < wyk) continue;
    ok[i] = 1;
    rep(idx, 1, sz(conds)) {
      if (conds[idx] == 0) continue;
      int ii = (i + idx) % DL;
      if (divs[ii] % conds[idx]) {
        ok[i] = false;
        break;
      }
    }
    if (ok[i]) {
      kt = i;
      ans.pb(i);
      
    }
  }
  // debug("eo think");
  int ileOk = 0;
  for (auto o : ok) {
    ileOk += o;
  }
  return ans;
}

int extract() {
  // cout << "extract " << endl;
  vi known(DL);
  rep(j, 0, DL) {
    known[j] = div_count(j);
  }
  // debug("before think");
  vi res = think(known.begin());
  // debug("after think", res);
  int start = 0;
  while (sz(res) > 1) {
    known.pb(div_count(DL + start));
    ++start;
    res = think(known.begin() + start);
  }
  return res[0] + start;
}

void solveBig() {
  int odp = extract();
  // debug("after extract");
  int div_odp = div_count(odp);

  // cout << "For num: " << odp << ", wyk: " << wyk << ", div_cnt: " << div_odp << endl;
  int min_wyk = 5;
  while (div_odp % (min_wyk + 1) != 0) {
    ++min_wyk;
  }
  // debug(min_wyk);
  queue<tuple<ll, int, int>> q;
  // MAX_WYKLADNIK = 48;
  rep(i, min_wyk, MAX_WYKLADNIK) {
    if (div_odp % (i + 1) == 0) {
      // dodaj mu ten wykladnik
      q.push({ odp, i, div_odp });
    }
  }
  int inqcount = 0;
  while (!q.empty()) {
    auto [num, wyk, prev_ans] = q.front(); q.pop();
    // debug("sciagam z kolej", num, wyk);
    if (wyk == MAX_WYKLADNIK) {
      // ans
      ll found_odp = (1ll << MAX_WYKLADNIK) - num;
      ll divek = div_count(num + (1LL << MAX_WYKLADNIK));
      if (divek != MAX_WYKLADNIK + 2) {
        continue;
      } else {
        Answer(found_odp);
        return;
      }
    }
    ll new_q = num + (1ll << wyk);
    ll new_ans = div_count(new_q);
    if (new_ans == prev_ans + 1) {
      // X + new_q == (1ll << wyk+1)
      // X = (1ll << (wyk + 1)) - new_q
      Answer((1ll << (wyk)) - num);
      return;
    }
    ++inqcount;
    // potencjalnie nowy wykladnik >= wyk + 1 => zobaczmy jaki powstal nowy wykladnik >= wyk + 1
    rep(nowy_wyk, wyk + 1, MAX_WYKLADNIK + 1) {
      if ((new_ans) % (nowy_wyk + 1) == 0) {
        debug("dalem pytanie: ", new_q, new_ans, nowy_wyk);
        q.push({ new_q, nowy_wyk, new_ans });
      }
    }
  }
}

void solve() {
  prep();
  int t = GetT();
  int q = GetQ();
  long long c = GetC();
  long long n = GetN();
  // cout << n << endl;
  if (n == 1000000000ll) {
    // cout << "zmniejszam max\n" << endl;
    MAX_WYKLADNIK = 30;
  }
  while (t--) {
    p.clear();
    rep(i, 0, DL) {
      p.pb(Ask(i));
    }
    int result = kmp();
    // cout << to_string(p) << endl;
    if (result != -1) {
      Answer(result);
    } else {
      solveBig();
    }
    maper.clear();
  }
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	// cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
}