#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,abm,bmi,bmi2")
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'032;
const int S = 4096;
struct node
{
bitset<S> *mask;
int child[4];
} pool[50000000];
int rt_ltr, rt_rtl;
int new_node()
{
static int nxt = 1;
return nxt++;
}
int rna_to_int(char c)
{
switch (c) {
case 'A': return 0;
case 'U': return 1;
case 'C': return 2;
case 'G': return 3;
}
return -1;
}
void trie_set(string s, int rt, int pos, int val)
{
int t = rt;
for (char c : s) {
int x = rna_to_int(c);
if (!pool[t].child[x])
return;
t = pool[t].child[x];
if (pool[t].mask)
(*pool[t].mask)[pos] = val;
}
}
int trie_insert(string s, int rt)
{
int t = rt;
for (char c : s) {
int x = rna_to_int(c);
if (!pool[t].child[x])
pool[t].child[x] = new_node();
t = pool[t].child[x];
}
if (!pool[t].mask)
pool[t].mask = new bitset<S>;
return t;
}
string joi_rna[N], cus_pre[N], cus_suf[N];
int cus_pre_node[N], cus_suf_node[N];
int ans[N];
int n, m;
void set_joi_intrvl(int l, int r, int val)
{
Loop (i,l,r) {
trie_set(joi_rna[i], rt_ltr, i-l, val);
reverse(joi_rna[i].begin(), joi_rna[i].end());
trie_set(joi_rna[i], rt_rtl, i-l, val);
reverse(joi_rna[i].begin(), joi_rna[i].end());
}
}
int fast_bs_cnt(bitset<S> *a, bitset<S> *b)
{
int *x = (int *)a;
int *y = (int *)b;
int ans = 0;
Loop (i,0,S/8/sizeof(int))
ans += __builtin_popcount(x[i] & y[i]);
return ans;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) {
cin >> joi_rna[i];
}
Loop (i,0,m) {
cin >> cus_pre[i];
cin >> cus_suf[i];
reverse(cus_suf[i].begin(), cus_suf[i].end());
}
rt_ltr = new_node();
rt_rtl = new_node();
Loop (i,0,m) {
cus_pre_node[i] = trie_insert(cus_pre[i], rt_ltr);
cus_suf_node[i] = trie_insert(cus_suf[i], rt_rtl);
}
for (int l = 0; l < n; l += S) {
int r = min(l+S, n);
set_joi_intrvl(l, r, 1);
Loop (cus,0,m) {
auto m1 = pool[cus_pre_node[cus]].mask;
auto m2 = pool[cus_suf_node[cus]].mask;
ans[cus] += fast_bs_cnt(m1, m2);
//ans[cus] += (*m1 & *m2).count();
}
set_joi_intrvl(l, r, 0);
}
Loop (i,0,m)
cout << ans[i] << '\n';
}
