#include using namespace std; using hash_value = pair, size_t>; class rolling_hash{ mt19937 mt; const uint32_t p[3] = {2111511013, 2131131137, 2147483647}; const int P_CNT = 1; uint64_t b[3], binv[3]; uint64_t mpow(uint64_t x, uint64_t y, uint32_t m){ if(y == 0) return 1; if(y == 1) return x%m; if(y%2 == 0) return mpow(x*x%m, y/2, m); return mpow(x*x%m, y/2, m) * x % m; } public: rolling_hash(){ random_device rd; mt.seed(rd()); for(int i=0;i<3;i++){ b[i] = 0; while(!b[i]) b[i] = mt() % p[i]; binv[i] = mpow(b[i], p[i]-2, p[i]); } } hash_value operator()(string s){ vector h = {0, 0, 0}; for(char c : s){ for(int i=0;i> s; cin >> m; for(int i=0;i> c[i]; rolling_hash rh; hash_value hash_s, hash_c; int ans = 0; for(int i=0;i