#include <bits/stdc++.h>
#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)
#define WTF cout << "WTF" << endl
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define s decond
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int L = 1e6 + 2;
const int N = 5e5 + 2;
const int M = 5e5 + 2;
const int LOG = 25;
const int B = 131;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
#define endl '\n'
#define lc now << 1
#define rc now << 1 | 1
int q, m, n;
LL tmp[L];
LL hsh[L], pw[L];
unordered_set<int> keep[M];
string ts[N], s;
struct IntMaxSeg {
int tree[N << 2];
int build(int now = 1, int ls = 0, int rs = n) {
if (ls == rs) return tree[now] = tmp[ls];
int mid = (ls + rs) >> 1;
return tree[now] = max(build(lc, ls, mid), build(rc, mid + 1, rs));
}
int get(int lq, int rq, int now = 1, int ls = 0, int rs = n) {
if (rq < lq || rq < ls || rs < lq) return 0;
if (lq <= ls && rs <= rq) return tree[now];
int mid = (ls + rs) >> 1;
return max(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
}
} dp[LOG];
void init() {
cin >> q >> m;
F0R(i, q) cin >> ts[i];
cin >> s;
n = s.length();
}
void calcHash(int id) {
LL h = 0;
F0R(i, (int)ts[id].length()) {
h = (h * B + ts[id][i]) % MOD;
keep[i + 1].insert(h);
}
return;
}
void mainHash() {
hsh[0] = s[0];
pw[0] = 1;
FOR(i, 1, n) {
hsh[i] = (hsh[i - 1] * B + s[i]) % MOD;
pw[i] = pw[i - 1] * B % MOD;
}
return;
}
inline LL getH(int l, int r) {
if (!l) return hsh[r];
return (hsh[r] - (hsh[l - 1] * pw[r - l + 1] % MOD) + MOD) % MOD;
}
void dpBase() {
F0R(i, n + 1) {
int l = i, r = n, mid;
while(l < r) {
mid = (l + r) >> 1;
if (keep[mid - i + 1].count(getH(i, mid))) l = mid + 1;
else r = mid;
}
tmp[i] = l;
}
dp[0].build();
}
void calcLayer(int id) {
F0R(i, n + 1) {
int x = dp[id - 1].get(i, i);
tmp[i] = dp[id - 1].get(i, x);
}
dp[id].build();
}
void handleQuery() {
int l, r;
cin >> l >> r;
r--;
int now = l;
int ans = INF, sum = 0;
if (dp[LOG - 1].get(l, l) <= r) {
cout << -1 << endl;
return;
}
R0F(i, LOG) {
int x = dp[i].get(l, now);
if (x > r)
ans = min(ans, sum + (1 << i));
else {
sum += (1 << i);
now = x;
}
}
cout << ans << endl;
}
int main() {
IOS;
init();
F0R(i, q) calcHash(i);
mainHash();
dpBase();
FOR(i, 1, LOG) calcLayer(i);
while(m--) handleQuery();
return 0;
}
