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
#include <bits/stdc++.h>
#include "dzilib.h"
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
vector<int> kmp(vv<int> &s){
		int n = ssize(s);
		vector<int> len(n, 0);
		for(int i = 1, j = len[i-1]; i < n; ++i, j = len[i-1]){
				while(j && s[i] != s[j]) j = len[j-1];
				if(s[i] == s[j]) ++j;
				len[i] = j;
		}
		return len;
}
void answer(){
		int T = GetT(), q = GetQ();
		ll c = GetC(), n = GetN();
		int N = int(n)+q/T, S = q/T;
		vv<int> d(N+1, 0);
		for(int i = 1; i <= N; ++i)
				for(int j = i; j <= N; j += i) ++d[j];
		vv<int> tmp;
		for(++T; --T; ){
				vv<int> t(S);
				for(int i = 0; i < ssize(t); ++i) t[i] = Ask(i);
				tmp = t;
				tmp.emplace_back(inf);
				for(int &u : d) tmp.emplace_back(u);
				//~ for(int i = 0; i < ssize(tmp); ++i) printf("%d ", tmp[i]);
				//~ pn;
				tmp = kmp(tmp);
				//~ for(int i = 0; i < ssize(tmp); ++i) printf("%d ", tmp[i]);
				//~ pn;
				int cnt = 0, ans = 0;
				for(int i = 0; i < ssize(tmp); ++i) if(tmp[i] == S) ++cnt, ans = i-2*S;
				Answer(ans);
		}
}
int main() {
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}