#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/**
* JOI - Selling RNA Strands
* Algoritm: 2D Range Counting (Offline with Fenwick Tree)
*/
struct StringNode {
string s;
int id;
};
struct Query {
int l1, r1, l2, r2, id;
};
struct Point {
int x, y;
};
struct Event {
int x, y1, y2, type, id; // type: -1 (chap chegara), 1 (o'ng chegara)
};
// Fenwick Tree (BIT) 1D diapazonda yig'indi hisoblash uchun
struct FenwickTree {
int n;
vector<int> tree;
FenwickTree(int n) : n(n), tree(n + 1, 0) {}
void update(int i, int delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
int query(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<StringNode> pref(N), suff(N);
for (int i = 0; i < N; i++) {
string s;
cin >> s;
pref[i] = {s, i};
reverse(s.begin(), s.end());
suff[i] = {s, i};
}
// Prefiks va Suffiks bo'yicha saralaymiz
sort(pref.begin(), pref.end(), [](const StringNode& a, const StringNode& b) {
return a.s < b.s;
});
sort(suff.begin(), suff.end(), [](const StringNode& a, const StringNode& b) {
return a.s < b.s;
});
// Har bir satrning yangi koordinatalarini aniqlaymiz
vector<int> pos_in_suff(N);
for (int i = 0; i < N; i++) {
pos_in_suff[suff[i].id] = i + 1; // 1-indexed
}
vector<Point> points(N);
for (int i = 0; i < N; i++) {
points[i] = {i + 1, pos_in_suff[pref[i].id]};
}
vector<Event> events;
vector<int> results(M, 0);
for (int i = 0; i < M; i++) {
string P, Q;
cin >> P >> Q;
reverse(Q.begin(), Q.end());
// Prefiks bo'yicha diapazonni topish
auto it1 = lower_bound(pref.begin(), pref.end(), StringNode{P, 0}, [](const StringNode& a, const StringNode& b) {
return a.s < b.s;
});
string P_limit = P; P_limit.back()++;
auto it2 = lower_bound(pref.begin(), pref.end(), StringNode{P_limit, 0}, [](const StringNode& a, const StringNode& b) {
return a.s < b.s;
});
// Suffiks bo'yicha diapazonni topish
auto it3 = lower_bound(suff.begin(), suff.end(), StringNode{Q, 0}, [](const StringNode& a, const StringNode& b) {
return a.s < b.s;
});
string Q_limit = Q; Q_limit.back()++;
auto it4 = lower_bound(suff.begin(), suff.end(), StringNode{Q_limit, 0}, [](const StringNode& a, const StringNode& b) {
return a.s < b.s;
});
int l1 = distance(pref.begin(), it1) + 1;
int r1 = distance(pref.begin(), it2);
int l2 = distance(suff.begin(), it3) + 1;
int r2 = distance(suff.begin(), it4);
if (l1 <= r1 && l2 <= r2) {
events.push_back({l1 - 1, l2, r2, -1, i});
events.push_back({r1, l2, r2, 1, i});
}
}
// X koordinatasi bo'yicha eventlarni saralaymiz
sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
return a.x < b.x;
});
FenwickTree ft(N);
int current_p = 0;
for (auto& e : events) {
while (current_p < N && points[current_p].x <= e.x) {
ft.update(points[current_p].y, 1);
current_p++;
}
int count = ft.query(e.y2) - ft.query(e.y1 - 1);
results[e.id] += e.type * count;
}
for (int res : results) {
cout << res << "\n";
}
return 0;
}
