#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define I inline
#define tp template <class T>
#define _r return *this
namespace IO {
	static constexpr int S = (1 << 21), dgt = 2, ir = 1;
	char b[S], *p1 = b, *p2 = b, pb[S], *p = pb;
	I void Fl() { fwrite(pb, 1, p - pb, stdout), p = pb; }
	struct Fr {
		I bool _b(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; }
		I char gc() { if (p1 == p2) p2 = (p1 = b) + fread(b, 1, S, stdin); return p1 == p2 ? ' ' : *p1++; }
		tp I Fr &operator>>(T &x) { char c = gc(); T f = 1; for (x = 0; !isdigit(c);) { if(c == '-') f = -1; c = gc(); } while (isdigit(c)) x = (x * 10) + (c ^ 48), c = gc(); x *= f; _r; }
		I Fr &operator>>(char *s) { int l = 0; char c; operator>>(c); for (; !_b(c); s[l++] = c, c = gc()) ; s[l] = '\0'; _r; }
		I Fr &operator>>(string &s) { s = ""; char c = gc(); while(_b(c)) c = gc(); while(!_b(c)) s += c, c = gc(); _r; }
		I Fr &operator>>(double &x) { double t = 1, s = 0; char c = gc(); for (x = 0; !isdigit(c); c = gc()) s = (c == '-'); for (; isdigit(c); c = gc()) x = x * 10 + (c - 48); if (c == '.') for (c = gc(); isdigit(c); c = gc()) x += (t /= 10.0) * (c - 48), s && (x = -x); _r; }
		I Fr &operator>>(char &c) { do c = gc(); while (_b(c)); _r; }
	} cin;
	struct Fw {
		I void pt(char c) { *p++ = c; if (p - pb == S) Fl(); }
		tp I Fw &operator<<(T x) { if (!x) { pt(48); _r; } if(x < 0) pt('-'), x = -x; int s[64], t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) pt(s[t--] + 48); _r; }
		I Fw &operator<<(char c) { pt(c); _r; } I Fw &operator<<(const char *s) { operator<<((char *)s); _r; }
		I Fw &operator<<(char *s) { int c = 0; while (s[c]) pt(s[c++]); _r; }
		I Fw &operator<<(double x) { int k = 0; if(x < 0) pt('-'), x = -x; if(ir) x += 5 * pow(10, -dgt - 1); operator<<(int(x)), pt('.'), x -= int(x); while (k++ < dgt) pt(int(x *= 10) + 48), x -= int(x); _r; }
		I Fw &operator<<(string s) { for(int i = 0; s[i] != '\0'; ++i) pt(s[i]); _r; } ~Fw() { Fl(); }
	} cout;
} ;

#define cin IO::cin
#define cout IO::cout

#define _f(i, a, b) for (int i = a; i <= b; ++i)
#define _d(i, a, b) for (int i = a; i >= b; --i)
using pii = pair<int, int>;
using ll = long long;
#define fi first
#define se second

static constexpr int N = 2e4 + 5, M = 1e5 + 5, L = 4e5 + 5, inf = 1e8;

int n, m, ind[N], ans[M], siz[N], ord[L << 1], dro[L << 1];
char ss[L];
vector<int> s[N], G[L << 1];
vector<pii> pos[N];
struct state {
	int len, link, nxt[2];
} st[L << 1];
int sz = 1;
int extend(int p, int c) {
	if(st[p].nxt[c]) {
		int q = st[p].nxt[c];
		if(st[q].len == st[p].len + 1) return q;
		else {
			int clone = ++sz;
			st[clone] = st[q], st[clone].len = st[p].len + 1;
			st[q].link = clone;
			while(p && st[p].nxt[c] == q) st[p].nxt[c] = clone, p = st[p].link;
			return clone;
		}
	}
	int cur = ++sz;
	st[cur].len = st[p].len + 1;
	while(p && !st[p].nxt[c]) st[p].nxt[c] = cur, p = st[p].link;
	if(!p) st[cur].link = 1;
	else {
		int q = st[p].nxt[c];
		if(st[q].len == st[p].len + 1) st[cur].link = q;
		else {
			int clone = ++sz;
			st[clone] = st[q], st[clone].len = st[p].len + 1;
			st[q].link = st[cur].link = clone;
			while(p && st[p].nxt[c] == q) st[p].nxt[c] = clone, p = st[p].link;
		}
	}
	return cur;
}
pii tr[N << 2];
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void pushup(int p) {
	tr[p] = min(tr[ls(p)], tr[rs(p)]);
}
void build(int p, int l, int r) {
	if(l == r) return tr[p] = {inf, l}, void();
	int mid = (l + r) >> 1;
	build(ls(p), l, mid), build(rs(p), mid + 1, r);
	pushup(p);
}
void modify(int p, int x, int l, int r, int k) {
	if(l == r) return tr[p].fi = k, void();
	int mid = (l + r) >> 1;
	if(x <= mid) modify(ls(p), x, l, mid, k);
	else modify(rs(p), x, mid + 1, r, k);
	pushup(p);
}
pii query(int p, int x, int y, int l, int r) {
	if(x <= l && r <= y) return tr[p];
	int mid = (l + r) >> 1;
	if(y <= mid) return query(ls(p), x, y, l, mid);
	if(x > mid) return query(rs(p), x, y, mid + 1, r);
	return min(query(ls(p), x, y, l, mid), query(rs(p), x, y, mid + 1, r));
}
set<pii> line[L << 1];
void insert(int x, int l, int r) {
	auto &t = line[x];
	auto it = t.lower_bound(make_pair(r + 1, inf));
	if(it == t.begin()) return t.emplace(l, r), void();
	--it;
	if(it->fi <= l && it-> se >= r) return ;
	while(it->se + 1 >= l) {
		if(it->se > r) r = it->se;
		if(it->fi < l) l = it->fi;
		it = t.erase(it);
		if(it == t.begin()) break;
		--it;
	}
	t.emplace(l, r);
}
void solve() {
	cin >> n >> m, build(1, 1, n);
	_f(i, 1, n) {
		cin >> (ss + 1);
		int lst = 1, l = strlen(ss + 1);
		_f(j, 1, l) s[i].emplace_back(ss[j] - '0'), lst = extend(lst, ss[j] - '0');
	}
	_f(i, 2, sz) G[st[i].link].emplace_back(i);
	_f(i, 1, m) {
		int l, r; cin >> l >> r;
		pos[l].emplace_back(make_pair(r, i));
	}
	_f(i, 1, n) {
		siz[i] = pos[i].size(), sort(pos[i].begin(), pos[i].end());
		if(siz[i]) modify(1, i, 1, n, pos[i].begin()->fi);
	}
	_f(i, 1, sz) ord[i] = i;
	sort(ord + 1, ord + sz + 1, [](int x, int y) { return st[x].len > st[y].len; });
	_f(i, 1, sz) dro[ord[i]] = i;
	_f(i, 1, n) {
		int lst = 1;
		for(int v : s[i]) lst = st[lst].nxt[v], insert(dro[lst], i, i);
	}
	_f(i, 1, sz) {
		for(int v : G[ord[i]]) {
			int to = dro[v];
			if(line[to].size() <= line[i].size()) {
				for(auto it : line[to]) insert(i, it.fi, it.se);
			} else {
				for(auto it : line[i]) insert(to, it.fi, it.se);
				swap(line[i], line[to]);
			}
			line[to].clear();
		}
		for(auto it : line[i]) {
			int l = it.fi, r = it.se;
			pii ret = query(1, l, r, 1, n);
			while(ret.fi <= r) {
				ans[pos[ret.se][ind[ret.se]].se] = st[ord[i]].len;
				++ind[ret.se];
				if(ind[ret.se] < siz[ret.se]) modify(1, ret.se, 1, n, pos[ret.se][ind[ret.se]].fi);
				else modify(1, ret.se, 1, n, inf);
				ret = query(1, l, r, 1, n);
			}
		}
	}
	_f(i, 1, m) cout << ans[i] << '\n';
}

signed main() {
	solve();
	return 0;
}

// by zzzcr.