#include<bits/stdc++.h>
#include "dzilib.h"
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
    return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
    os<<"{";
    for(int i=0; i<V.size(); i++){
        if(i)os<<" ";
        os<<V[i];
    }
    os<<"}";
    return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll los(ll a, ll b){
    if(a>b)swap(a, b);
    unsigned long long t=rng();
    t<<=31;
    t+=rng();
    return a+(t%(b-a+1));
}

int ile(ll a){
	return __builtin_ctzll(a);
}
/*
g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20
*/
int main() {
	//deb(ile(1), ile(6),ile(4));
	//return 0;
    int tt = GetT();
    int Q = GetQ();
    long long C = GetC();
    long long N = GetN();
    while(tt--) {
        ll x=los(0, 10*N);
        ll potm=1, potM=1024;
        vector<ll> V(potM);
        iota(all(V), 0);
        vector<pair<ll, int>> ans;
        while(true){
        	//x=((V[0]+potm-1)/potm)*potm;
        	deb(ans.size());
        	if((V[0]+x)%potm){
        		ll t=(V[0]+x)%potm;
        		x+=potm-t;
        	}
        	ans.pb({x, Ask(x)});
        	x++;
        	//deb(ans, potm, potM, V);
        	vector<ll> V2;
        	for(ll &i:V){
        		int a=ile(ans.back().st+i);
        		//assert((1ll<<a)>=potm);
        		if((1ll<<a)<potM && ans.back().nd%(a+1)){

        		}
        		else V2.pb(i);
        	}
        	V=V2;
        	V2.clear();
        	//deb(V, potm, potM);
        	bool b=1;
        	for(ll &i:V){
        		if((i-V[0])%(2*potm)){
        			b=0;
        		}
        	}
        	if(b){
        		for(ll &i:V){
        			if(i+potM<=N)V2.pb(i+potM);
        		}
        		for(ll &i:V2)V.pb(i);
        		V2.clear();
        		//deb(V);
        		potm*=2;
        		potM*=2;
        		for(ll &i:V){
	        		b=1;
	        		for(auto &j:ans){
	        			int a=ile(j.st+i);
	        			if((1ll<<a)<potM && j.nd%(a+1)){
	        				b=0;
	        			}
        			}
        			if(b)V2.pb(i);
        		}
        		V=V2;
        		//assert(V.size());
        	}
        	if(V.size()==1 && potM>=N)break;
        }
        Answer(V[0]);
    }
    return 0;
}