// INOI20_dabbeh
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod[] = {1000010549, 1000 * 1000 * 1000 + 7};
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
const int prm[] = {727, 883};
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const int MAXN = 300100;
const int LOGN = 22;
struct chash
{
ll operator()(const pii &p) const
{
return (ll)p.fr * 1000000000 + p.sc;
}
};
int n, q;
char s[MAXN];
gp_hash_table<pii, bool, chash> st;
int pw[2][MAXN];
int hsh[2][MAXN];
int dp[LOGN][MAXN];
inline int gethash(int t, int l, int r)
{
return (mod[t] + (hsh[t][r + 1] - hsh[t][l] * (ll)pw[t][r - l + 1]) % mod[t]) % mod[t];
}
#define gethashpr(l, r) {gethash(0, (l), (r)), gethash(1, (l), (r))}
struct SEG
{
int seg[2 * MAXN];
inline void build(int *dp)
{
FOR(i, 0, MAXN) seg[i + MAXN] = dp[i];
for (int i = MAXN - 1; i > 0; i--) seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
inline int get(int l, int r)
{
r++;
int res = -INF;
for (l += MAXN, r += MAXN; l < r; l /= 2, r /= 2)
{
if (l % 2) res = max(res, seg[l++]);
if (r % 2) res = max(res, seg[--r]);
}
return res;
}
} seg[LOGN];
int32_t main(void)
{
fast_io;
int tmp;
cin >> tmp >> q;
while (tmp--)
{
string t;
cin >> t;
int h[2] = {};
for (char c : t)
{
FOR(t, 0, 2)
h[t] = (h[t] * (ll)prm[t] + c) % mod[t];
st.insert({{h[0], h[1]}, 0});
}
}
cin >> s;
n = strlen(s);
FOR(t, 0, 2)
{
pw[t][0] = 1;
FOR(i, 1, MAXN) pw[t][i] = pw[t][i - 1] * (ll)prm[t] % mod[t];
FOR(i, 1, n + 1) hsh[t][i] = (hsh[t][i - 1] * (ll)prm[t] + s[i - 1]) % mod[t];
}
FOR(i, 0, n)
{
int l = 0, r = n - i + 1;
while (r - l > 1)
{
int mid = (r + l) / 2;
if (st.find(gethashpr(i, i + mid - 1)) != st.end()) l = mid;
else r = mid;
}
dp[0][i] = i + l - 1;
}
FOR(i, 1, LOGN)
{
seg[i - 1].build(dp[i - 1]);
FOR(j, 0, n)
{
dp[i][j] = seg[i - 1].get(j, dp[i - 1][j] + 1);
}
}
seg[LOGN - 1].build(dp[LOGN - 1]);
while (q--)
{
int l, r;
cin >> l >> r;
r--;
int ptr = l;
int cost = 0;
for (int i = LOGN - 1; i >= 0; i--)
{
int fw = seg[i].get(l, ptr);
if (fw >= r) continue;
cost += (1 << i);
ptr = fw + 1;
}
if (cost > n) cout << "-1\n";
else cout << cost + 1 << endl;
}
return 0;
}
