#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef string str;
typedef pair<str, int> T;
const int N = 1e5 + 10;
int n, m;
vector<T> V;
int fl = false;
char c = 'a'; //'#'
bool CMP(T A, T B){
if(fl) c = '#';
else c = 'a';
int ln = min(A.F.size(), B.F.size());
if(A.S < 0) A.F += c;
else A.F += 'A';
if(B.S < 0) B.F += c;
else B.F += 'A';
return A < B;
/*
for(int i = 0; i < ln; i++){
if(A.F[i] != B.F[i]) return A.F[i] < B.F[i];
}
if(A.S < 0 && B.S < 0) return A.F.size() < B.F.size();
if(A.S > 0 && B.S > 0) return A.F.size() < B.F.size();
//if(fl) return A.S < 0;
//if(A.S < 0 && B.S > 0 && A.F.size() > B.F.size()) return false;
//if(A.S > 0 && B.S < 0 && A.F.size() < B.F.size()) return true;
if(fl) return A.S < B.S;
return A.S > B.S;
*/
}
str R[N], P[N], Q[N];
int st[N], SQ[N], FQ[N], SQ2[N], FQ2[N];
vector<int> ord;
int seg[20][N];
int LG(int id, int x, int L, int R, int d){
int idx = lower_bound(seg[d] + L, seg[d] + R, x) - seg[d];
return idx - L;
}
void Build(int id, int L, int R, int d = 0){
if(L + 1 == R){
seg[d][L] = ord[L];
return ;
}
int mid = (L + R) >> 1;
Build(id << 1, L, mid, d + 1);
Build(id << 1 | 1, mid, R, d + 1);
merge(seg[d + 1] + L, seg[d + 1] + mid, seg[d + 1] + mid, seg[d + 1] + R, seg[d] + L);
return ;
}
int Query(int id, int l, int r, int x, int L, int R, int d = 0){
if(r <= L || R <= l) return 0;
if(l <= L && R <= r) return LG(id, x, L, R, d); //{Less(id, x), Great(id, x)};
int mid = (L + R) >> 1;
int A = Query(id << 1, l, r, x, L, mid, d + 1);
int B = Query(id << 1 | 1, l, r, x, mid, R, d + 1);
return A + B;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> R[i];
for(int j = 1; j <= m; j++) cin >> P[j] >> Q[j];
for(int i = 1; i <= n; i++) V.pb({R[i], i});
for(int i = 1; i <= m; i++) V.pb({P[i], -i});
sort(all(V), CMP);
int la = 1;
for(auto &x : V){
if(x.S < 0) FQ[-x.S] = la;
else st[x.S] = la ++;
}
//cerr << '\n';
//for(auto x : V) cerr << x.F << " " << x.S << '\n';
fl = true;
sort(all(V), CMP);
la = 1;
for(auto &x : V){
if(x.S < 0) SQ[-x.S] = la;
else la ++;
}
//cerr << '\n';
//for(auto x : V) cerr << x.F << " " << x.S << '\n';
//cerr << '\n';
/*
for(int i = 1; i <= n; i++) cerr << st[i] << ' ';
cerr << '\n';
for(int i = 1; i <= m; i++) cerr << "[" << SQ[i] << ", " << FQ[i] << ")\n";
cerr << '\n';
for(auto x : V) cerr << x.F << " " << x.S << '\n';
*/
V.clear();
for(int i = 1; i <= n; i++){
reverse(all(R[i]));
V.pb({R[i], st[i]});
}
for(int i = 1; i <= m; i++){
reverse(all(Q[i]));
V.pb({Q[i], -i});
}
sort(all(V), CMP);
for(auto &x : V){
if(0 < x.S) ord.pb(x.S);
else SQ2[-x.S] = ord.size();
}
fl = false;
sort(all(V), CMP);
ord.clear();
for(auto &x : V){
if(0 < x.S) ord.pb(x.S);
else FQ2[-x.S] = ord.size();
}
//for(auto x : ord) cerr << x << ' ';
//cerr << '\n';
//for(int i = 1; i <= m; i++) cerr << "[" << SQ[i] << ", " << FQ[i] << ") [" << SQ2[i] << ", " << FQ2[i] << ")\n";
//cerr << '\n';
Build(1, 0, n);
for(int i = 1; i <= m; i++){
int res = 0;
//for(int j = SQ2[i]; j < FQ2[i]; j++) res += (SQ[i] <= ord[j] && ord[j] < FQ[i]);
cout << Query(1, SQ2[i], FQ2[i], FQ[i], 0, n) - Query(1, SQ2[i], FQ2[i], SQ[i], 0, n) << '\n';
}
return 0;
}
/*
*/
