#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())
#define Mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MXN = 5e5+5, MXL = 3e5+5, LOG = 20;
ll mod[2] = {1000000007, 998244353}, p[2][MXN];
bool is_prime(int x) {
for(int i=2; i*i<=x; i++)
if(x%i == 0)
return 0;
return 1;
}
void generate() {
for(int t : {0, 1}) {
p[t][0] = 1;
p[t][1] = rng()%50 + 100;
while(p[0][1]==p[1][1] || !is_prime(p[t][1])) p[t][1]++;
for(int i=2; i<MXN; i++) p[t][i] = p[t][i-1]*p[t][1]%mod[t];
}
}
ll h[2][MXN];
void init(string s) {
for(int t : {0, 1})
for(int i=1; i<=SZ(s); i++)
h[t][i] = (h[t][i-1]*p[t][1]+s[i-1])%mod[t];
}
pll geth(int l, int r) {
return Mp(
(h[0][r-1] - h[0][l-1]*p[0][r-l]%mod[0] + mod[0])%mod[0],
(h[1][r-1] - h[1][l-1]*p[1][r-l]%mod[1] + mod[1])%mod[1]
);
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ h2;
}
};
int n, m, L, nxt[MXL], par[LOG][MXL];
string s;
unordered_map<pll,bool,pair_hash> hashs;
pii seg[MXL<<2];
void Build(int l=0, int r=L+1, int id=1) {
if(r-l == 1) {
seg[id] = Mp(nxt[l], l);
return;
}
Build(l, mid, lc);
Build(mid, r, rc);
seg[id] = max(seg[lc], seg[rc]);
}
pii Get(int s, int e, int l=0, int r=L+1, int id=1) {
if(s<=l && r<=e) return seg[id];
if(e<=mid) return Get(s, e, l, mid, lc);
if(s>=mid) return Get(s, e, mid, r, rc);
return max(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
generate();
cin >> n >> m;
for(int i=0; i<n; i++) {
cin >> s;
init(s);
for(int i=1; i<=SZ(s); i++)
hashs[geth(1, i+1)]=1;
}
cin >> s;
init(s);
L = SZ(s);
for(int i=0; i<L; i++) {
int l=i-1, r=L;
while(r-l>1)
if(hashs.find(geth(i+1, mid+2)) != hashs.end()) l = mid;
else r = mid;
nxt[i] = l+1;
}
nxt[L] = L;
Build();
for(int i=0; i<=L; i++) {
int p = Get(i, nxt[i]+1).Y;
par[0][i] = (p == i ? L+1 : p);
}
par[0][L+1] = L+1;
for(int i=1; i<LOG; i++)
for(int j=0; j<=L+1; j++)
par[i][j] = par[i-1][par[i-1][j]];
while(m--) {
int L, R;
cin >> L >> R;
// cout << "-1\n";
int ans=0, v=L;
for(int i=LOG-1; i>=0; i--)
if(par[i][v] < R) {
ans += 1<<i;
v = par[i][v];
}
if(nxt[v]<R) {
cout << "-1\n";
continue;
}
if(ans == 0) {
cout << "1\n";
continue;
}
int d = ans-1;
v = L;
for(int i=0; i<LOG; i++)
if(d>>i & 1)
v = par[i][v];
cout << ans + (nxt[v]<R) << '\n';
}
return 0;
}
