#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
struct Node
{
int ends;
int nxt[4];
};
Node emptyNode= {0,{0,0,0,0}};
int val(char c)
{
if (c=='A')
return 0;
if (c=='G')
return 1;
if (c=='C')
return 2;
if (c=='U')
return 3;
}
struct ceva
{
int lin;
int delta;
int poz;
};
struct altceva
{
int col;
int delta;
};
const int inf=1e9;
int aib[800005];
int tinp[800005];
int tins[800005];
int toutp[800005];
int touts[800005];
int ans[100005];
vector<altceva> updates[800005];
vector<ceva> queries[800005];
int timer,timer1,timer2;
class Trie
{
public:
int sz;
Node trie[800005];
map<string,int>endies;///asta se putea face mult mai bine dar cred ca intra si asa
void init()
{
sz=0;
trie[0]=emptyNode;
}
void ins(string s, int dir)
{
int i,node,c;
node=0;
if (dir==1)
{
for (i=0; i<s.size(); i++)
{
c=val(s[i]);
if (trie[node].nxt[c]==0)
{
sz++;
trie[node].nxt[c]=sz;
trie[sz]=emptyNode;
}
node=trie[node].nxt[c];
}
}
else
{
for (i=s.size()-1;i>=0;i--)
{
c=val(s[i]);
if (trie[node].nxt[c]==0)
{
sz++;
trie[node].nxt[c]=sz;
trie[sz]=emptyNode;
}
node=trie[node].nxt[c];
}
}
trie[node].ends++;
endies[s]=node;
}
pair<int,int> interval(string s, int dir)
{
int i,node,c;
node=0;
for (i=0; i<s.size(); i++)
{
c=val(s[i]);
if (trie[node].nxt[c]==0)
{
return {inf,inf};
}
node=trie[node].nxt[c];
}
if (dir==0)
return {tins[node],touts[node]};
else
return {tinp[node],toutp[node]};
}
} triep,tries;
void dfsp(int node)
{
timer++;
tinp[node]=timer;
int i,child;
for (i=0; i<4; i++)
{
child=triep.trie[node].nxt[i];
if (child!=0)
{
dfsp(child);
}
}
toutp[node]=timer;
}
void dfss(int node)
{
timer++;
tins[node]=timer;
int i,child;
for (i=0; i<4; i++)
{
child=tries.trie[node].nxt[i];
if (child!=0)
{
dfss(child);
}
}
touts[node]=timer;
}
void update(int idx, int delta)
{
while (idx<=timer1)
{
aib[idx]+=delta;
idx+=idx&(-idx);
}
}
int query(int idx)
{
int ans;
ans=0;
while (idx>0)
{
ans+=aib[idx];
idx-=idx&(-idx);
}
return ans;
}
signed main()
{
/*
ifstream fin("arbore.in");
ofstream fout("arbore.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,i,j,othernode;
pair<int,int> res1,res2;
string s,pref,suff;
cin >> n >> m;
triep.init();
tries.init();
for (i=1; i<=n; i++)
{
cin >> s;
triep.ins(s,1);
tries.ins(s,-1);
}
timer=0;
dfss(0);
timer1=timer;
timer=0;
dfsp(0);
timer2=timer;
for (i=1; i<=m; i++)
{
cin >> pref >> suff;
reverse(suff.begin(),suff.end());
res1=triep.interval(pref,1);
res2=tries.interval(suff,0);
/*
debugs(pref);
debugs(res1.first);
debug(res1.second);
debugs(suff);
debugs(res2.first);
debug(res2.second);
*/
if (res1.first==inf && res1.second==inf || res2.first==inf && res2.second==inf)
{
ans[i]=0;
}
else
{
queries[res1.second].push_back({res2.second,1,i});///dreapta jos
queries[res1.second].push_back({res2.first-1,-1,i});///stanga jos
queries[res1.first-1].push_back({res2.second,-1,i});///dreapta sus
queries[res1.first-1].push_back({res2.first-1,1,i});///stanga sus
}
}
for (auto x : triep.endies)
{
/*
debugs(x.first);
debugs(tinp[x.second]);
*/
othernode=tries.endies[x.first];
//debug(tins[othernode]);
//debug(tries.trie[othernode].ends);
updates[tinp[x.second]].push_back({tins[othernode],tries.trie[othernode].ends});
}
for (i=1; i<=timer2; i++)
{
for (auto x : updates[i])
{
/*
debugs(i);
debug(x);
*/
update(x.col,x.delta);
}
for (auto x : queries[i])
{
/*
debugs(x.poz);
debugs(i);
debugs(x.lin);
debug(query(x.lin));
*/
ans[x.poz]+=query(x.lin)*x.delta;
}
}
for (i=1; i<=m; i++)
{
cout << ans[i] << "\n";
}
return 0;
}
