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
#include "dzilib.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN = 2e6+7;
const pii MOD = {1e9+7, 1e9+696969};
const pii P = {9319, 8527};
pll powers[MAXN];
pll H[MAXN];
int T[MAXN];
int divs[MAXN];
int n,q;
int Q = 99;
map<pll, int> ans;
void solve_case(){
    pll h = {0, 0};
    for(int i=0;i<Q;++i){
        int x = Ask(i);
        h.first = (h.first + x * powers[i+1].first) % MOD.first;
        h.second = (h.second + x * powers[i+1].second) % MOD.second;
    }
    h.first = h.first * powers[n].first % MOD.first;
    h.second = h.second * powers[n].second % MOD.second;
    Answer(ans[h]);
}
int main()
{
	ios_base::sync_with_stdio(0);
    for(int i=2;i<MAXN;++i){
        if(T[i]) continue;
        for(int j=i;j<MAXN;j+=i) if(!T[j]) T[j] = i;
    }
    for(int i=1;i<MAXN;++i){
        int x = i;
        int last = -1, cnt = 0;
        divs[i] = 1;
        while(T[x]){
            if(T[x] != last){
                divs[i] *= (cnt+1);
                last = T[x];
                cnt = 1;
            }else ++cnt;
            x /= T[x];
        }
        divs[i] *= (cnt+1);
    }
    powers[0] = {1, 1};
    for(int i=1;i<MAXN;++i){
        powers[i].first = powers[i-1].first * P.first % MOD.first;
        powers[i].second = powers[i-1].second * P.second % MOD.second;
    }
    for(int i=1;i<MAXN;++i){
        H[i].first = (H[i-1].first + divs[i] * powers[i].first) % MOD.first;
        H[i].second = (H[i-1].second + divs[i] * powers[i].second) % MOD.second;
    }
	int t = GetT();
    n = GetN();
    q = GetQ();
    for(int i=1;i<=n;++i){
        int l = i, r = l + Q - 1;
        pll tmp = {0, 0};
        tmp.first = (H[r].first - H[l-1].first + MOD.first);
        if(tmp.first < 0) tmp.first += MOD.first;
        tmp.second = (H[r].second - H[l-1].second + MOD.second);
        if(tmp.second < 0) tmp.second += MOD.second;
        int diff = n + Q - r;
        tmp.first = tmp.first * powers[diff].first % MOD.first;
        tmp.second = tmp.second * powers[diff].second % MOD.second;
        ans[tmp] = i;
    }
    while(t--) solve_case();
}