#include <iostream> // Usuń
#include <vector>
#include "dzilib.h"

using namespace std;

const int n = 1'000'000;
const int magic_const = 17;

vector<int> dividers(n + magic_const);
vector<int> primes;

void fill_dividers_and_primes()
{
    for (int i = 1; i < n + magic_const; i++)
        for (int j = i; j < n + magic_const; j += i)
            dividers[j]++;
    
    for (int i = 2; i < n + magic_const; i++)
        if (dividers[i] == 2)
            primes.push_back(i);
}

inline bool correct_answer(int x, vector<int>& wyniki)
{
    for (int i = 0; i < wyniki.size(); i++)
        if (dividers[x + i] != wyniki[i])
            return false;
    return true;
}

int get_answer(vector<int>& wyniki)
{
    for (int i = 1; i <= n; i++)
        if (correct_answer(i, wyniki))
            return i;
    return -1;
}

long long fast_exponential(long long a, long long b, long long mod)
{
    long long result = 1;

    while (b > 0)
    {
        if (b % 2 == 1)
            result = (__int128_t(result) * a) % mod;
        a = (__int128_t(a) * a) % mod;
        b = b / 2;
    }

    return result;
}

bool miller_rabin_test(long long a, long long p)
{
    int k = 0;
    long long d = p - 1;

    while (d % 2 == 0)
    {
        k++;
        d = d / 2;
    }

    long long x = fast_exponential(a, d, p);

    if (x == 1 or x == p - 1) return true;

    for (int i = 0; i < k - 1; i++)
    {
        x = (__int128_t(x) * x) % p;

        if (x == 1) return false;
        if (x == p - 1) return true;
    }

    return false;
}

bool is_prime(long long p)
{
    if (p == 2) return true;
    if (p % 2 == 0 or p == 1) return false;

    const vector<long long> va = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    for (long long a: va)
    {
        if (a == p) return true;
        if (not miller_rabin_test(a, p))
            return false;
    }
    return true;
}

long long discrete_sqrt(long long n)
{
    long long l = 1;
    long long r = 1e9;

    while (l <= r)
    {
        long long m = (l + r) / 2;

        if (m * m < n)
            l = m + 1;
        else
            r = m - 1;
    }

    return l;
}

int number_of_divisors(long long n)
{
    int i = 0;
    int answer = 1;

    while (primes[i] * primes[i] * primes[i] <= n)
    {
        int power = 0;

        while (n % primes[i] == 0)
        {
            n /= primes[i];
            power++;
        }

        answer *= power + 1;
        i++;
    }

    if (is_prime(n))
        answer *= 2;
    else
    {
        long long sqrt_n = discrete_sqrt(n);

        if (sqrt_n * sqrt_n == n and is_prime(sqrt_n))
            answer *= 3;
        else if (n != 1)
            answer *= 4;
    }

    return answer;
}

void generate_all_divs(int n, vector<vector<int>>& result)
{
    if (n > 1)
    {
        for (int i = 1; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                vector<vector<int>> r;

                if (n / i != i)
                {
                    r.clear();
                    generate_all_divs(i, r);

                    for (auto& v : r)
                    {
                        v.push_back(n / i);
                        result.push_back(v);
                    }
                }

                if (i != 1)
                {
                    generate_all_divs(n / i, r);

                    for (auto& v : r)
                    {
                        v.push_back(i);
                        result.push_back(v);
                    }
                }
            }
        }
    }
    else
    {
        result.push_back({});
    }
}

long long power(long long t, long long a, int b, long long limit)
{
    long long result = t;

    for (int i = 0; i < b; i++)
    {
        if (result > limit / a)
            return limit + 1;

        result = result * a;
    }

    return result;
}

void generate_all_numbers(vector<int> format, vector<long long> &result, long long limit, int current = 1, int i = 0, int j = 0)
{
    // i - index in format
    // j - index in primes

    if (i == format.size())
    {
        result.push_back(current);
        return;
    }

    int quicktest = 0;

    for (int ii = i; ii < format.size(); ii++)
        quicktest += format[ii] - 1;
    
    if (j < primes.size() and power(current, primes[j], quicktest, limit) > limit) return;

    for (int jj = j; jj < primes.size(); jj++)
    {
        long long next = power(current, primes[jj], format[i] - 1, limit);

        if (next <= limit)
        {
            generate_all_numbers(format, result, limit, next, i + 1, jj+1);
        }
        else
        {
            return;
        }
    }
}

inline bool correct_answer(long long x, vector<pair<long long, long long>>& wyniki)
{
    for (int i = 0; i < wyniki.size(); i++)
        if (number_of_divisors(x + wyniki[i].first) != wyniki[i].second)
            return false;
    return true;
}

int main()
{
    int liczba_testow = GetT();
    int liczba_prob = GetQ();
    long long ograniczenie_na_x = GetN();
    long long ograniczenie_na_y = GetC();
  
    fill_dividers_and_primes();

    if (ograniczenie_na_x <= 1'000'000)
    {
        while (liczba_testow--)
        {
            vector<int> wyniki(magic_const);

            for (int i = 0; i < magic_const; i++)
                wyniki[i] = Ask(i);
            
            Answer(get_answer(wyniki));
        }
    }
    else
    {
        int prob_na_test = liczba_prob / liczba_testow;

        long long another_magic_const = 123;
        vector<pair<long long, long long>> wyniki(prob_na_test);

        for (int i = 0; i < prob_na_test; i++)
        {
            wyniki[i] = {i + another_magic_const, Ask(i + another_magic_const)};
        }

        int max_ind = 0;

        for (int i = 1; i < prob_na_test; i++)
            if (wyniki[i].second > wyniki[max_ind].second)
                max_ind = i;
        
        vector<vector<int>> format;
        vector<long long> candidates;

        generate_all_divs(wyniki[max_ind].second, format);

        for (auto& v : format)
            generate_all_numbers(v, candidates, ograniczenie_na_x + wyniki[max_ind].first);
        
        for (long long x : candidates)
        {
            x -= wyniki[max_ind].first;

            if (correct_answer(x, wyniki))
            {
                Answer(x);
                break;
            }
        }
        
    }
    
    return 0;
}