1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include "dzilib.h"
#include <map>

using ll = long long;

const int N = 1 << 20;
const int SQRT = 1 << 10;
const int Q = 100;
const int W = Q + 1;

int S[N];
std::map<int, int> P;
int D[N + W + 7];
int Ans[Q];
int K[N];

void sieve() {
  for (int i = 2; i < SQRT; i++) {
    if (S[i] == 0) {
      S[i] = i;

      for (int j = i * i; j < N; j += i)
        S[j] = i;
    }
  }

  for (int i = 2; i < N; i++)
    if (S[i] == 0)
        S[i] = i;
}

void factor(int x) {
    while (x > 1) {
        P[S[x]]++;
        x /= S[x];
    }
}

void KMP() {
  K[0] = -1;
  K[1] = 0;

  for (int i = 2; i < N; i++) {
    int kndt = K[i-1];

    while (kndt >= 0 && D[i] != D[kndt + 1]) {
      kndt = K[kndt];
    }

    K[i] = kndt + 1;

    if (K[i] == Q) {
      Answer(i - Q - Q - 1);
      return;
    }
  }
}

int main() {
  int t = GetT();
  int q = GetQ();
  ll c = GetC();
  ll n = GetN();

  if (n == 1e5) {
    while (t--) {
      if (Ask(0) == 1) {
        Answer(1);
      } else {
        ll y = 0;
        ll y1, y2;

        while ((Ask(y) & 1) == 0) {
          y++;
        }

        y1 = y;
        y = y + y + 3;

        while ((Ask(y) & 1) == 0) {
          y++;
        }

        y2 = y;
        ll z = (y2 - y1 - 1) / 2;

        Answer(z * z - y1);
      }
    }
  } else {
    sieve();

    for (int i = 1; i < N; i++) {
      P.clear();
      factor(i);
      int d = 1;

      for (auto& it : P)
        d *= it.second + 1;

      D[i + W] = d;
    }

    D[0] = -1;
    D[W] = -2;

    while (t--) {
      for (int i = 1; i <= Q; i++) {
        D[i] = Ask(i);
      }

      KMP();
    }
  }

  return 0;
}