#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
struct segtree
{
int size;
vi arr;
vb active;
void init(int n)
{
size = 1;
while (size < n)
size *= 2;
arr.assign(2 * size, 0);
active.assign(2 * size, false);
}
void doInc(int x, int amount)
{
if (x < size || active[x])
arr[x] += amount;
}
void propagate(int x)
{
if (x < size)
{
doInc(2 * x, arr[x]);
doInc(2 * x + 1, arr[x]);
arr[x] = 0;
}
}
void increment(int l, int r) { increment(l, r, 1, 0, size); }
void increment(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
{
doInc(x, 1);
return;
}
if (r <= lx || rx <= l)
return;
int m = (lx + rx) / 2;
increment(l, r, 2 * x, lx, m);
increment(l, r, 2 * x + 1, m, rx);
}
void setState(int x, bool state) { setState(x, state, 1, 0, size); }
void setState(int i, bool state, int x, int lx, int rx)
{
propagate(x);
if (rx - lx == 1)
{
active[x] = state;
return;
}
int m = (lx + rx) / 2;
if (i < m)
setState(i, state, 2 * x, lx, m);
else
setState(i, state, 2 * x + 1, m, rx);
}
int query(int i) { return query(i, 1, 0, size); }
int query(int i, int x, int lx, int rx)
{
propagate(x);
if (rx - lx == 1)
return arr[x];
int m = (lx + rx) / 2;
if (i < m)
return query(i, 2 * x, lx, m);
else
return query(i, 2 * x + 1, m, rx);
}
};
vvi S; // Sortiment von der Company
vvi P, Q; // Prefixes and suffixes
vi Qin, Qout; // in idx and out idx for the range sums
segtree seg;
struct node
{
int idx = 0; // of this node
node *children[4] = {nullptr, nullptr, nullptr, nullptr};
vi fixe; // suffixe or prefixe
vi S; // together with suffixes there are sorting
};
struct trie
{
node *root = new node();
void insert(vi &word, int id, bool type) { insert(root, 0, word, id, type); }
void insert(node *r, int idx, vi &word, int id, int type)
{ // id to append to the fixe (type 0) and S (type 1)
if (idx == sz(word))
{
if (type == 0)
r->fixe.push_back(id);
else
r->S.push_back(id);
return;
}
int next = word[idx];
if (r->children[next] == nullptr)
r->children[next] = new node();
insert(r->children[next], idx + 1, word, id, type);
}
};
trie Tsuff, Tpref;
void dfsInit(node *r, int &idx)
{
for (int q : r->fixe)
Qin[q] = ++idx;
r->idx = idx; // knowing the correct prefix idx
for (int i = 0; i < 4; ++i)
if (r->children[i] != nullptr)
dfsInit(r->children[i], idx);
for (int q : r->fixe)
Qout[q] = ++idx;
}
void answer(node *r, vi &word)
{
int idx = 0;
int i = 0;
while (r != nullptr)
{
idx = r->idx;
if (i >= sz(word))
break;
r = r->children[word[i++]];
}
seg.increment(0, idx + 1);
}
void dfsAnswer(node *r)
{
for (int qid : r->fixe)
{
seg.setState(Qin[qid], true);
seg.setState(Qout[qid], true);
}
for (int sid : r->S)
{
answer(Tpref.root, S[sid]);
}
for (int i = 0; i < 4; ++i)
if (r->children[i] != nullptr)
dfsAnswer(r->children[i]);
for (int qid : r->fixe)
{
seg.setState(Qin[qid], false);
seg.setState(Qout[qid], false);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
S.resize(N);
string rna, kundeP, kundeQ;
vi decode(128);
decode['A'] = 0, decode['C'] = 1, decode['G'] = 2, decode['U'] = 3;
for (int i = 0; i < N; ++i)
{
cin >> rna;
for (char c : rna)
S[i].push_back(decode[c]);
reverse(all(S[i]));
Tsuff.insert(S[i], i, 1);
reverse(all(S[i]));
}
P.resize(M), Q.resize(M);
for (int i = 0; i < M; ++i)
{
cin >> kundeP >> kundeQ;
for (char c : kundeP)
P[i].push_back(decode[c]);
Tpref.insert(P[i], i, 0);
for (char c : kundeQ)
Q[i].push_back(decode[c]);
reverse(all(Q[i]));
Tsuff.insert(Q[i], i, 0);
}
int idx = 0;
Qin.resize(M), Qout.resize(M);
dfsInit(Tpref.root, idx);
++idx;
seg.init(idx);
dfsAnswer(Tsuff.root);
for (int q = 0; q < M; ++q)
cout << seg.query(Qin[q]) - seg.query(Qout[q]) << "\n";
return 0;
}
