#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct Trie
{
    Trie() : nchildren(0)
    {
        for(int i=0; i<26; i++)
            children[i] = NULL;
    }

    ~Trie()
    {
        //for(int i=0; i<26; i++)
        //            delete children[i];
        // Stack overflows!
    }
    
    int nchildren;    
    Trie *children[26];    
};

void insert(Trie *t, const std::string &s)
{
    int L = s.length();
    for(int pos=0; pos<L; pos++)
    {
        t->nchildren++;        
        int idx = s[pos]-'a';
        if(!t->children[idx])
            t->children[idx] = new Trie();
        t = t->children[idx];
    }
    t->nchildren++;
}

int query(Trie *t, const std::string &s)
{
    int L = s.length();
    for(int pos=0; pos<L; pos++)
    {
        int idx = s[pos]-'a';
        if(!t->children[idx])
            return 0;
        t = t->children[idx];
    }
    return t->nchildren;
}

std::string alternate(const std::string &s)
{
    int L = s.length();
    std::string result;
    result.resize(2*L);
    for(int i=0; i<L; i++)
    {
        result[2*i] = s[i];
        result[2*i+1] = s[L-i-1];
    }
    return result;
}

int main()
{
    int n, q;
    std::cin >> n >> q;
    
    Trie prefixT;
    Trie suffixT;
    Trie bothT;
    for(int i=0; i<n; i++)
    {
        std::string s;
        std::cin >> s;
        insert(&prefixT, s);
        std::string r(s.rbegin(), s.rend());
        insert(&suffixT, r);
        insert(&bothT, alternate(s));
    }
    
    for(int i=0; i<q; i++)
    {
        std::string command, prefix, suffix;
        std::cin >> command >> prefix >> suffix;
        
        std::reverse(suffix.begin(), suffix.end());

        int L = prefix.length();
        std::string both;
        both.resize(2*L);
        for(int j=0; j<L; j++)
        {
            both[2*j] = prefix[j];
            both[2*j+1] = suffix[j];
        }
        
        if(command == std::string("AND"))
        {
            std::cout << query(&bothT, both) << std::endl;
        }
        else if(command == std::string("OR"))
        {
            std::cout << query(&prefixT, prefix) + query(&suffixT, suffix) - query(&bothT, both) << std::endl;
        }
        else
        {
            std::cout << query(&prefixT, prefix) + query(&suffixT, suffix) - 2*query(&bothT, both) << std::endl;
        }
    }    
}