test

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;


template<ll MOD, ll p>
struct THash {
    int n;
    vector<int> t;
    vector<int> pw;
    THash(const vector<int>& s)
        : n(s.size())
        , t(n)
        , pw(n + 1)
    {
        pw[0] = 1;
        t[0] = s[0];
        for (int i = 1; i < n; i++) {
            t[i] = (s[i] + t[i - 1] * p) % MOD;
            pw[i] = pw[i - 1] * p % MOD;
        }
    }
    int operator () (int l, int r) {
        if (r < l) return 0;
        return (t[r] + MOD - (l ? t[l - 1] * 1LL * pw[r - l + 1] % MOD : 0)) % MOD;
    }
};


template<ll mod, int n, ll m>
void Test() {
    vector<int> arr(n);
    const int Size = n / 1000;
    vector<int> brr(Size * 2);
    for (int i = 0; i < n; i++) {
        arr[i] = (rand() % m) + 1;
    }
    for (int i = 0; i < Size; i++) {
        brr[i] = (rand() % m) + 1;
        brr[i + Size] = brr[i];
    }
    unordered_set<int> hshs;
    THash<mod, m + 1> a(arr);
    THash<mod, m + 1> b(brr);
    for (int i = 0; i < Size; i++) {
        hshs.insert(b(i, i + Size - 1));
    }
    vector<bool> cyc(n, false);
    for (int i = 0; i + Size <= n; i++) {
        if (hshs.count(a(i, i + Size - 1))) {
            cyc[i] = true;
        }
    }

    for (int i = 0; i < n; i++) {
        if (cyc[i]) {
            bool ans = false;
            for (int start = 0; start < Size && !ans; start++) {
                bool current = true;
                for (int j = 0; j < Size && current; j++) {
                    current &= arr[i + j] == brr[start + j];
                }
                ans |= current;
            }
            if (!ans) {
                cout << "FAILED!!!" << endl;
                assert(false);
            }
        }
    }
    cout << "passed " << accumulate(all(cyc), 0) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    const int T = 500;
    const ll mod = 1e9 + 9;
    const int n = 1e4;
    const ll m = 2;
    cout << "Test cases : " << T << endl;
    cout << "Modulo : " << mod << endl;
    cout << "Length of a : " << n << endl;
    cout << "Length of b : " << n / 1000 << endl;
    cout << "Alphabet : " << m << endl;

    for (int i = 0; i < T; i++) {
        cout << i + 1 << " ";
        Test<mod, n, m>();
    }
}