## 题解

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 1000000007
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 100005
int n, m;
int ch[N << 1][2], pre[N << 1], step[N << 1], x, cnt = 1, last = 1, sz[N << 1];
inline void ins (int x)
{
int p = last, np = ++cnt;
last = cnt; step[np] = step[p] + 1; sz[np] = 1;
while (p && !ch[p][x])
ch[p][x] = np, p = pre[p];
if (!p)
pre[np] = 1;
else
{
int q = ch[p][x];
if (step[q] == step[p] + 1)
pre[np] = q;
else
{
int nq = ++cnt;
step[nq] = step[p] + 1;
fo (i, 0, 1) ch[nq][i] = ch[q][i];
pre[nq] = pre[q]; pre[q] = pre[np] = nq;
while (ch[p][x] == q) ch[p][x] = nq, p = pre[p];
}
}
}
char c;
struct node {
int x, y, v;
friend bool operator < (node x, node y)
{
return x.x > y.x;
}
} t[N * 40], q[N];
std::set<int> s[N << 1];
int a[N << 1], b[N << 1], tot;
#define itset std::set<int>::iterator
inline void merge ()
{
fo (i, 1, cnt) ++a[step[i]];
fo (i, 1, n) a[i] += a[i - 1];
fo (i, 1, cnt) b[a[step[i]]--] = i;
fd (i, cnt, 2)
{
int u = b[i], p = pre[u];
if (s[u].size() > s[p].size()) std::swap(s[u], s[p]);
for (itset it = s[u].begin(); it != s[u].end(); ++it)
{
itset pos = s[p].lower_bound(*it);
if (pos != s[p].end()) t[++tot] = (node) {*it, *pos, step[p]};
if (pos != s[p].begin()) t[++tot] = (node) {*(--pos), *it, step[p]};
}
for (itset it = s[u].begin(); it != s[u].end(); ++it) s[p].insert(*it);
}
}
int ans[N], T[N];
inline void update (int u, int val) { for (int i = u; i <= n; i += lowbit(i)) T[i] = std::max(T[i], val); }
inline int query (int u) { int ret = 0; for (int i = u; i; i -= lowbit(i)) ret = std::max(T[i], ret); return ret; }
int main ()
{
scanf("%d %d", &n, &m);
fo (i, 1, n)
{
c = getchar();
while (!isdigit(c)) c = getchar();
s[cnt + 1].insert(i);
ins(c == '1');
}
merge();
fo (i, 1, m)
{
scanf("%d %d", &q[i].x, &q[i].y);
q[i].v = i;
}
std::sort(q + 1, q + m + 1); std::sort(t + 1, t + tot + 1);
int j = 1;
fo (i, 1, m)
{
while (j <= tot && q[i].x <= t[j].x) update(t[j].y, t[j].v), ++j;
ans[q[i].v] = query(q[i].y);
}
fo (i, 1, m) printf("%d\n", ans[i]);
}