#include using namespace std; class rolling_hash{ mt19937 mt; const uint32_t p[3] = {2111511013, 2131131137, 2147483647}; uint64_t b[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]; } } vector operator()(string s){ vector h = {0, 0, 0}; for(char c : s){ for(int i=0;i<3;i++) h[i] = (h[i]*b[i]%p[i]+c) % p[i]; } return h; } // x が y の中に何回出現するか uint32_t contain(const string &x, const string &y){ size_t xl = x.size(), yl = y.size(); if(xl > yl) return 0; uint64_t bl[3]; for(int i=0;i<3;i++) bl[i] = mpow(b[i], xl, p[i]); vector xh(3, 0), yh(3, 0); for(int i=0;i<3;i++){ for(size_t j=0;j> s; cin >> m; for(int i=0;i> c[i]; uint64_t ans = 0; for(int i=0;i