//
// Stvoreno Energom o 24.10.23. 12:33:22
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
//#define len(a) (int) (a.size())
#define fir first
#define sec second
#define mp make_pair
#define pb push_back

using namespace std;

#ifdef Energy_is_not_over
#define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0)
#define LOG(...) print(#__VA_ARGS__" ::",__VA_ARGS__)<<endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (0)
#define LOG(...)
#endif

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

const int max_n = 1000111, max_q = 500, max_buf = 80'000'000, inf = 1000111222;

int cntlen[max_n];
int start[max_n];
int fin[max_n];
int cur[max_n];
int d[max_buf];

vector<int> z_function(const string& s) {
    vector<int> z(s.size(), 0);
    z[0] = 0;
    int l = 0, r=  0;
    for (int i = 1; i < s.size(); ++i) {
        z[i] = 0;
        if (i <= r) {
            z[i] = min(z[i - l], r - i + 1);
        }
        while (i + z[i] < s.size() && s[i + z[i]] == s[z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }
    return z;
}

bool CALC = 1;
int C = 0;

int get_z(vector<int> const& z, int i) {
    return (0 <= i && i < z.size()) ? z[i] : 0;
}


void output(int l, int r, int len) { // [i..i + 2 * len) for i = l..r
    if (CALC) {
        ++C;
//        LOG(l, r, len);
        cntlen[len]++;
    } else {
        d[cur[len]] = l;
        d[cur[len] + 1] = r;
        cur[len] += 2;
    }
}

void gener(int shift, bool left, int cntr, int l, int k1, int k2) {
    int L1 = max(1, l - k2), R1 = min(l - left, k1);
    if (L1 <= R1) {
        if (left) {
            output(shift + cntr - R1, shift + cntr - L1, l);
        } else {
            output(shift + (cntr - l + 1) - R1, shift + (cntr - l + 1) - L1, l);
        }
    }
}

void find_repetitions(const string &s, int shift = 0) {
    int n = s.size();
    if (n == 1) {
        return;
    }
    int nu = n / 2, nv = n - n / 2;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());
    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);
    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);
    for (int cntr = 0; cntr < n; ++cntr) {
        int L, k1, k2;
        if (cntr < nu) {
            L = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            L = cntr - nu + 1;
            k1 = get_z(z3, 2 * nu + nv - cntr);
            k2 = get_z(z4, cntr - nu + 1);
        }
        if (k1 + k2 >= L) {
            gener(shift, cntr < nu, cntr, L, k1, k2);
        }
    }
}

string s;
int n, q;
vector<int> all_l;

bool check1(int len, int pos) {
    int* from = d + start[len];
    int* to = d + fin[len];
    while(from != to) {
        if (*from <= pos && *(from + 1) >= pos) {
            return true;
        }
        from += 2;
    }
    return false;
}

int check2(int len, int l, int r) {
    int* from = d + start[len];
    int* to = d + fin[len];
    int mn = inf;
    while(from != to) {
        if (*from >= l && *from <= r && *from < mn) {
            mn = *from;
        }
        from += 2;
    }
    return mn;
}

pair<int, int> solve(int from, int to) {
    for (int len : all_l) {
        int to1 = to - 2 * len + 1;
        if (to1 < from) continue;
        if (check1(len, from)) {
            return make_pair(len, from);
        }
        int res = check2(len, from, to1);
        if (res != inf) {
            return make_pair(len, res);
        }
    }
    return make_pair(0, from);
}

//bool deb =0;

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    cin >> s;
//    s = string(1e6, 'a');
    find_repetitions(s);
//    cout << C << endl;
//    return 0;
    int cur_start = 0;
    for (int l = 0; l < s.size(); ++l) {
        if (cntlen[l] > 0) {
            all_l.push_back(l);
        }
        start[l] = cur_start;
        fin[l] = start[l] + cntlen[l] * 2;
        cur[l] = start[l];
        cur_start = fin[l];
    }
    sort(all_l.begin(), all_l.end());
    reverse(all_l.begin(), all_l.end());
    CALC = 0;
    find_repetitions(s);
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        auto p = solve(a, b);
        cout << p.first << ' ' << p.second + 1 << "\n";
    }


    return 0;
}