#include #include #include using namespace std; using ll = long long; #line 1 "hash/hashint.hpp" using namespace std; #include #include #include struct hashint{ using ull = unsigned long long; ull x; const static ull mod = (1ll<<61) - 1; hashint():x(0){} hashint(ull _x):x(_x){} hashint& operator+=(const hashint a) { x += a.x; if(x>=mod) x -= mod; return (*this); } hashint& operator-=(const hashint a) { x += mod - a.x; if(x>=mod) x -= mod; return (*this); } hashint& operator*=(const hashint a) { x = mul(x,a.x); return (*this); } hashint operator+(const hashint a) const { hashint res(*this); return res += a; } hashint operator-(const hashint a) const { hashint res(*this); return res -= a; } hashint operator*(const hashint a) const { hashint res(*this); return res *= a; } ull val(){ return x; } bool operator==(const hashint a) const { return x == a.x; } bool operator<(const hashint a) const { return x < a.x; } static ull mul(const ull a,const ull b) {\ ull au = a >> 31; ull ad = a & ((1ull<<31)-1); ull bu = b >> 31; ull bd = b & ((1ull<<31)-1); ull res = au * bu * 2; ull mid = au * bd + ad * bu; ull midu = mid >> 30; ull midd = mid & ((1ull<<30)-1); res += midu + midd * (1ull<<31); res += ad * bd; res = (res>>61) + (res&((1ull<<61)-1)); if(res>=mod) res -= mod; return res; } static ull modpow(ull x,ull k){ ull res = 1; while(k){ if(k&1) res = mul(res,x); x = mul(x,x); k >>= 1; } return x; } static bool isPrimitive(ull x) { for (auto &now:vector{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321}) if (modpow(x,(mod-1)/now)<=1) return false; return true; } static hashint get_base(){ long long seed = chrono::duration_cast(chrono::system_clock::now().time_since_epoch()).count(); mt19937_64 rnd(seed); uniform_int_distribution now(1,mod-1); ull base{}; while (true){ base = now(rnd); if(isPrimitive(base)) break; } return base; } }; /** * @brief Hashint * @docs docs/hash/hashint.md */ #line 2 "hash/rollinghash.hpp" #include template struct rolling_hash{ using ull = unsigned long long; struct hash{ H x,b; hash():x(0),b(1){} hash(ull _x,ull _b):x(_x),b(_b){} hash(H _x,H _b):x(_x),b(_b){} ull val(){ return x.val(); } hash operator+=(const hash a){ x = x * a.b + a.x; b *= a.b; return (*this); } hash operator+(const hash a){ hash res(*this); return res += a; } bool operator==(const hash a){ return x == a.x; } bool operator<(const hash a){ return x < a.x; } }; int n; static H base; vector sum,powb; rolling_hash(T x){ n = x.size(); sum = vector(n+1,0); powb = vector(n+1,1); for(int i = 0;i1){ int mid = (right+left) / 2; if(get(a,a+mid).val()==get(b,b+mid).val()) left = mid; else right = mid; } return left; } }; using rhash = rolling_hash; using hint = rhash::hash; template<> hashint rhash::base = hashint::get_base(); /** * @brief Rolling Hash * @docs docs/hash/rollinghash.md */ #include int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n; cin>>n; vector s(n); for(int i = 0;i>s[i]; vector rh; for(int i = 0;i,int> memo; ll m,x,d; cin>>m>>x>>d; ll ans = 0; for(ll k = 1;k<=m;k++){ ll i = (x/(n-1)) + 1; ll j = (x%(n-1)) + 1; if(i>j) swap(i,j); else j = j + 1; x = (x+d) % (n*(n-1)); if(memo.find(make_pair(i,j))!=memo.end()){ ans += memo[make_pair(i,j)]; //cout<1){ ll mid = (right+left) / 2; if(rh[i].get(0,mid)==rh[j].get(0,mid)) left = mid; else right = mid; } memo[make_pair(i,j)] = left; ans += left; } cout<