#pragma GCC optimize ("O3")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int LOG = 20;

struct SparseTable
{
	VI t[LOG];

	void push_back(int v)
	{
		int i = SZ(t[0]);
		t[0].PB(v);
		FOR (j, 0, LOG - 1) 
			t[j + 1].PB(min(t[j][i], t[j][max(0, i - (1 << j))]));
	}
	// [l, r)
	int query(int l, int r)
	{
		assert(l < r && r <= SZ(t[0]));
		int i = 31 - __builtin_clz(r - l);
		return min(t[i][r - 1], t[i][l + (1 << i) - 1]);
	}
};

void countSort(VI& p, const VI& c)
{
	int n = SZ(p);
	VI cnt(n);
	FOR (i, 0, n)
		cnt[c[i]]++;
	VI pos(n);
	FOR (i, 1, n)
		pos[i] = pos[i - 1] + cnt[i - 1];
	VI p2(n);
	for (auto x : p)
	{
		int i = c[x];
		p2[pos[i]++] = x;
	}
	p = p2;
}

VI suffixArray(VI s)
{
	// strictly smaller than any other element
	s.PB(-1);
	int n = SZ(s);
	VI p(n), c(n);
	iota(ALL(p), 0);
	sort(ALL(p), [&](int i, int j)
	{
		return s[i] < s[j];
	});
	int x = 0;
	c[p[0]] = 0;
	FOR (i, 1, n)
	{
		if (s[p[i]] != s[p[i - 1]])
			x++;
		c[p[i]] = x;
	}
	int k = 0;
	while ((1 << k) < n)
	{
		FOR (i, 0, n)
			p[i] = (p[i] - (1 << k) + n) % n;
		countSort(p, c);
		VI c2(n);
		PII pr = {c[p[0]], c[(p[0] + (1 << k)) % n]};
		FOR (i, 1, n)
		{
			PII nx = {c[p[i]], c[(p[i] + (1 << k)) % n]};
			c2[p[i]] = c2[p[i - 1]];
			if (pr != nx)
				c2[p[i]]++;
			pr = nx;
		}
		c = c2;
		k++;
	}
	p.erase(p.begin());
	s.pop_back();
	return p;
}
		
struct LCP
{
	int n;
	VI s, sa, rnk, lcp;
	SparseTable st;

	LCP(VI _s): n(SZ(_s)), s(_s)
	{
		sa = suffixArray(s);
		rnk.resize(n);
		FOR (i, 0, n)
			rnk[sa[i]] = i;
		lcpArray();
		FOR (i, 0, n - 1)
			st.PB(lcp[i]);
	}

	void lcpArray()
	{
		lcp.resize(n - 1);
		int h = 0;
		FOR (i, 0, n)
		{
			if (h > 0)
				h--;
			if (rnk[i] == 0)
				continue;
			int j = sa[rnk[i] - 1];
			for (; j + h < n && i + h < n; h++)
			{
				if (s[j + h] != s[i + h])
					break;
			}
			lcp[rnk[i] - 1] = h;
		}
	}
	int queryLcp(int i, int j)
	{
		if (i == n || j == n)
			return 0;
		assert(i != j); // return n - i ????
		i = rnk[i];
		j = rnk[j];
		if (i > j)
			swap(i, j);
		// query [i, j)
		return st.query(i, j);
	}
};


vector<tuple<int, int, int>> solve(VI s) 
{
    int n = SZ(s);
    LCP lcp(s); reverse(ALL(s));
    LCP rev(s); reverse(ALL(s));

    vector<tuple<int, int, int>> runs;
	FOR(inv, 0, 2)
    {
		VI st = {n};
		auto pop = [&](int i)
		{
			int j = st.back();
			int dist = j - i;
			int distPrev = st[SZ(st) - 2] - j;
			int distMn = min(dist, distPrev);

			int len = lcp.queryLcp(i, j);
			if(len >= distMn && dist < distPrev)
				return true;
			if(len < distMn && ((s[i + len] < s[j + len]) ^ inv))
				return true;
			return false;
		};
	
		RFOR(i, n, 0)
        {
            while (SZ(st) > 1 && pop(i))
				st.pop_back();
            int j = st.back();
            st.PB(i);

            int x = (i > 0 && s[i - 1] == s[j - 1]) ? rev.queryLcp(n - i, n - j) : 0;
			int dist = j - i;

            if (x < dist) 
            {
                int y = lcp.queryLcp(i, j);
                if (x + y >= dist) 
                    runs.push_back({dist, i - x, j + y});
            }
        }
    }
    assert(SZ(runs) <= SZ(s));
    sort(runs.begin(), runs.end());
	runs.erase(unique(runs.begin(), runs.end()), runs.end());
	assert(SZ(runs) <= SZ(s) / 2);
    return runs;
}



int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	VI vs(SZ(s));
	FOR(i, 0, SZ(s))
		vs[i] = s[i] - 'a';
	
	auto res = solve(vs);
	

	while(q--)
	{
		int L, R;
		cin >> L >> R;
		L--;
		PII ans = MP(0, -L);
		for(auto [len, l, r] : res)
		{
			l = max(l, L);
			r = min(r, R);
			
			if(l + 2 * len <= r)
			{
				int cnt = (r - l) / (2 * len);
				
				ans = max(ans, MP(cnt * len, -l));
			}
		}
		cout << ans.F << " " << -ans.S + 1 << "\n";
	}
	
	

	
	
	return 0;
}