namespace aho {
    const int N = 4000000, C = 2;
    int trans[N][C];
    int lst = 1;
    int fail[N];
    int term[N];

    void build(const vector<string> &v) {
        rep(i, sz(v)) {
            int s = 0;
            repi(j, v[i]) {
                int &t = trans[s][j=='o'];
                if (!t) t = lst++;
                s = t;
            }
            term[s] = i+1;
        }

        queue<int> q; rep(i, C) if (trans[0][i]) q.push(trans[0][i]);
        while(sz(q) > 0) {
            int t = q.front(); q.pop();
            rep(i, C) if (trans[t][i]) {
                int p = fail[t];
                while(p and !trans[p][i]) p = fail[p];
                p = trans[p][i];
                fail[trans[t][i]] = p;
                assert(term[p] == 0);
                q.push(trans[t][i]);
            }
        }
    }

    bool query(string &s){
        int p = 0;
        for(auto &i : s){
            while(p and !trans[p][i]) p = fail[p];
            p = trie[p][i];
            if(term[p]) return 1;
        }
        return 0;
    }
}