#include using namespace std; //cout << fixed << setprecision(10); #define rep(i, N) for(int i=0;i<(N);i++) #define all(x) (x).begin(),(x).end() #define popcount(x) __builtin_popcount(x) using ll = long long; using ld = long double; using graph = vector>; using P = pair; const int inf = 1e9; const ll infl = 1e18; const ld eps = ld(0.000000001); const long double pi = acos(-1); const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const int dx[4] = { 1,0,-1,0 }; const int dy[4] = { 0,1,0,-1 }; templatevoid chmax(T&x,T y){if(xvoid chmin(T&x,T y){if(x>y)x=y;} class RollingHash { static const ll mod = 1e9 + 7; const ll base; vector powers; //base^i static inline ll generate_base() { mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution rand((ll)1, (ll)mod - 1); return rand(engine); } ll mod_pow(ll base, ll exp) { if(base==0)return 0; ll ans = 1; base %= mod; while (exp > 0) { if (exp & 1) { ans *= base; ans %= mod; } base *= base; base %= mod; exp >>= 1; } return ans; } //idの振り方 ll mapping(char c) { return (c - 'A' + 1); } void expand(int siz) { if (powers.size() < siz + 1) { int pre_siz = powers.size(); powers.resize(siz + 1); for (int i = pre_siz; i <= siz; i++) { powers[i] = (powers[i - 1] * base) % mod; } } } public: RollingHash(ll base = generate_base()) :base(generate_base()), powers{ 1 } { } vector build(string& s) { vector hash(s.size() + 1); for (int i = 1; i <= s.size(); i++) { hash[i] = (hash[i-1] * base % mod + mapping(s[i-1])) % mod; } return hash; } ll range(vector&hash,int l, int r) { //expand(r - l); return ((hash[r] + mod - hash[l] * mod_pow(base,r - l)) % mod + mod) % mod; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin>>s; int m; cin>>m; vector c_hash(m); RollingHash rh; rep(i,m){ string c; cin>>c; vector tmp=rh.build(c); c_hash[i]=tmp.back(); } int len=s.size(); auto res=rh.build(s); unordered_map cnt; for(int i=0;i