#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
int start, end;
TrieNode() : start(-1), end(-1) {}
};
class Trie {
public:
TrieNode* root;
int timer;
Trie() {
root = new TrieNode();
timer = 0;
}
TrieNode* insert(const string& word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children.find(ch) == node->children.end()) {
node->children[ch] = new TrieNode();
}
node = node->children[ch];
}
return node;
}
void eulerTour(TrieNode* node) {
node->start = timer++;
for (auto& child : node->children) {
eulerTour(child.second);
}
node->end = timer - 1;
}
void build(const vector<string>& words) {
for (const string& word : words) {
insert(word);
}
eulerTour(root);
}
};
class FenwickTree {
public:
vector<int> tree;
int size;
FenwickTree(int n) : size(n) {
tree.resize(n + 1, 0);
}
void update(int index, int delta) {
while (index <= size) {
tree[index] += delta;
index += index & -index;
}
}
int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
int rangeQuery(int left, int right) {
return query(right) - query(left - 1);
}
};
struct Event {
int x, type, y1, y2, queryIndex;
bool operator<(const Event& other) const {
if (x != other.x) return x < other.x;
return type < other.type;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<string> rna_sequences(n);
vector<pair<string, string>> queries(m);
for (int i = 0; i < n; ++i) {
cin >> rna_sequences[i];
}
for (int i = 0; i < m; ++i) {
cin >> queries[i].first >> queries[i].second;
}
Trie prefixTrie, suffixTrie;
prefixTrie.build(rna_sequences);
vector<string> reversed_rna_sequences(n);
for (int i = 0; i < n; ++i) {
reversed_rna_sequences[i] = string(rna_sequences[i].rbegin(), rna_sequences[i].rend());
}
suffixTrie.build(reversed_rna_sequences);
vector<Event> events;
vector<int> results(m, 0);
vector<pair<int, int>> points;
for (int i = 0; i < n; ++i) {
TrieNode* pNode = prefixTrie.insert(rna_sequences[i]);
TrieNode* sNode = suffixTrie.insert(reversed_rna_sequences[i]);
points.emplace_back(pNode->start, sNode->start);
}
for (int i = 0; i < m; ++i) {
TrieNode* pNode = prefixTrie.insert(queries[i].first);
TrieNode* sNode = suffixTrie.insert(string(queries[i].second.rbegin(), queries[i].second.rend()));
if (pNode->start == -1 || sNode->start == -1) {
continue;
}
events.push_back({pNode->start, 1, sNode->start, sNode->end, i});
events.push_back({pNode->end + 1, 2, sNode->start, sNode->end, i});
}
for (const auto& p : points) {
events.push_back({p.first, 3, p.second, p.second, -1});
}
sort(events.begin(), events.end());
FenwickTree bit(suffixTrie.timer);
for (const auto& event : events) {
if (event.type == 1) {
results[event.queryIndex] -= bit.rangeQuery(event.y1, event.y2);
} else if (event.type == 2) {
results[event.queryIndex] += bit.rangeQuery(event.y1, event.y2);
} else if (event.type == 3) {
bit.update(event.y1, 1);
}
}
for (int i = 0; i < m; ++i) {
cout << results[i] << endl;
}
return 0;
}
