#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 200'447;
const int AL = 26;

struct Node
{
	int cnt;
	int nxt[AL];
	
	Node()
	{
		cnt = 0;
		fill(nxt, nxt + AL, -1);
	}
};

struct Trie
{
	vector<Node> t;
	
	Trie(): t(1) {}
	
	void add(string s)
	{
		int v = 0;
		for (auto c : s)
		{
			if (t[v].nxt[c - 'a'] == -1)
			{
				t[v].nxt[c - 'a'] = SZ(t);
				t.PB(Node());
			}
			v = t[v].nxt[c - 'a'];
			t[v].cnt++;
		}
	}
	int get(string s)
	{
		int v = 0;
		for (auto c : s)
		{
			v = t[v].nxt[c - 'a'];
			if (v == -1)
				return 0;
		}
		return t[v].cnt;
	}
	
};

struct Segtree
{
	int n;
	vector<ordered_set> t;
	
	Segtree(int _n)
	{
		n = 1;
		while (n < _n)
			n *= 2;
		t.resize(2 * n - 1);
	}
	
	void upd(int v, int tl, int tr, int i, int x)
	{	
		t[v].insert(x);
		if (tl + 1 == tr)
			return;
		int tm = (tl + tr) / 2;
		if (i < tm)
			upd(v * 2 + 1, tl, tm, i, x);
		else
			upd(v * 2 + 2, tm, tr, i, x);
	}
	void upd(int i, int x)
	{
		upd(0, 0, n, i, x);
	}
	int query(int v, int tl, int tr, int l, int r, int L, int R)
	{
		if (l <= tl && tr <= r)
			return t[v].order_of_key(R + 1) - t[v].order_of_key(L);
		if (l >= tr || tl >= r)
			return 0;
		int tm = (tl + tr) / 2;
		return query(v * 2 + 1, tl, tm, l, r, L, R) + 
			   query(v * 2 + 2, tm, tr, l, r, L, R);
	}
	int query(int l, int r, int L, int R)
	{
		return query(0, 0, n, l, r, L, R);
	}
	
};

int lb(VI& idx, vector<string>& v, string& s)
{
	int l = -1;
	int r = SZ(v);
	while (l + 1 < r)
	{
		int m = (l + r) / 2;
		if (s <= v[idx[m]])
			r = m;
		else
			l = m;
	}
	return r;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	vector<string> v(n), r(n);
	Trie t1, t2;
	FOR (i, 0, n)
	{
		cin >> v[i];
		r[i] = v[i];
		reverse(ALL(r[i]));
		t1.add(v[i]);
		t2.add(r[i]);
	}
	VI idx(n);
	iota(ALL(idx), 0);
	sort(ALL(idx), [&](int i, int j)
	{
		return v[i] < v[j];
	});
	VI val(n);
	FOR (i, 0, n)
		val[idx[i]] = i;

	VI idxr(n);
	iota(ALL(idxr), 0);
	sort(ALL(idxr), [&](int i, int j)
	{
		return r[i] < r[j];
	});
	Segtree st(n + 1);
	FOR (i, 0, n)
	{
		st.upd(i, val[idxr[i]]);
	}
	
	
	FOR (i, 0, q)
	{
		string t, p, s;
		cin >> t >> p >> s;
		reverse(ALL(s));
		//cerr << t1.get(p) << ' ' << t2.get(s) << '\n';
		int plus = t1.get(p) + t2.get(s);
		int L = lb(idx, v, p);
		
		bool isPref = L == n ? false : p == v[idx[L]].substr(0, SZ(p));
		p[SZ(p) - 1]++;
		int R = lb(idx, v, p);
		
		int Lr = lb(idxr, r, s);
		s[SZ(s) - 1]++;
		int Rr = lb(idxr, r, s);
		
		
		int all = isPref ? st.query(Lr, Rr, L, R - 1) : 0;
		//cerr << L << ' ' << R << ' ' << Lr << ' ' << Rr << '\n';
		//cerr << plus << ' ' << all << '\n';
		if (t == "AND")
			cout << all << '\n';
		else if (t == "OR")
			cout << plus - all << '\n';
		else
			cout << plus - 2 * all << '\n';
		//cerr << "\n\n";
	}
	
	
	return 0;
}