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
#include <bits/stdc++.h>
#include "dzilib.h"
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,int> PLI;
typedef pair<int,long long> PIL;
const int mod = 1e9+7;
const unsigned long long B = 1000696969;

int pr[1200005];
int num_div[1200005];
mt19937 gen(2137);
unsigned long long rd[1200005];
map<unsigned long long, int> res;

void init(int n, int qq){
    pr[1] = 1;
    for(int i=2;i<=n;i++){
        if(pr[i] != 0) continue;
        pr[i] = i;
        for(int j=2*i;j<=n;j+=i){
            if(pr[j] == 0) pr[j] = i;
        }
    }
    num_div[1] = 1;
    for(int i=2;i<=n;i++){
        int p = pr[i];
        int k = i;
        int cnt = 0;
        while(pr[k] == p){
            cnt++;
            k /= p;
        }
        num_div[i] = num_div[k]*(cnt+1);
    }
    for(int i=1;i<=n;i++) rd[i] = ((long long)1e9)*gen()+gen();

    // for(int i=1;i<=100;i++) cout<<pr[i]<<" "; cout<<endl;
    // for(int i=1;i<=100;i++) cout<<num_div[i]<<" "; cout<<endl;

    unsigned long long hash = 0;
    unsigned long long Bqq = 1;
    for(int i=1;i<qq;i++) Bqq = Bqq*B;
    for(int i=1;i<=qq;i++){
        hash = hash*B + rd[num_div[i]];
    }
    for(int i=1;i<=n;i++){
        // if(res[hash] != 0){
        //     cout<<i<<" "<<res[hash]<<" "<<qq<<endl;
        // }
        // assert(res[hash] == 0);
        res[hash] = i;
        hash -= Bqq*rd[num_div[i]];
        hash = hash*B + rd[num_div[i+qq]];
    }
}

void solve(int n, int qq){
    unsigned long long hash = 0;
    for(int i=0;i<qq;i++){
        hash = hash*B + rd[Ask(i)];
    }
    Answer(res[hash]);
}

int main(){
    // ios_base::sync_with_stdio(0);
    int t = GetT();
    int n = GetN();
    int q = GetQ();
    int qq = q/t;

    init(n+60000, qq);

    while(t--){
        solve(n, qq);
    }
}