#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
ll clz(ll N)
{
ll idx{};
for (int i = 0; i < 32; i++)
{
if (N & (1LL << i))
idx = i;
}
return 31 - idx;
}
namespace SuffixArray
{
const int maxN = 4e5 + 10;
string S;
ll N, gap;
int SA[maxN], pos[maxN], tmp[maxN];
vector<int> lcp(maxN);
vector<vector<int>> m;
bool sufCmp(int i, int j)
{
if (pos[i] != pos[j])
return pos[i] < pos[j];
i += gap;
j += gap;
return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}
void buildSA()
{
N = S.size();
for (int i{}; i < N; i++)
SA[i] = i,
pos[i] = S[i];
for (gap = 1;; gap *= 2)
{
sort(SA, SA + N, sufCmp);
for (int i{}; i < N - 1; i++)
tmp[i + 1] = tmp[i] + sufCmp(SA[i], SA[i + 1]);
for (int i{}; i < N; i++)
pos[SA[i]] = tmp[i];
if (tmp[N - 1] == N - 1)
break;
}
}
void buildLCP()
{
for (int i = 0, k = 0; i < N; ++i)
{
if (pos[i] != N - 1)
{
for (int j = SA[pos[i] + 1]; S[i + k] == S[j + k];)
++k;
lcp[pos[i]] = k;
if (k)
--k;
}
}
int LOG
= ceil(log2
(N
)) + 1; m.resize(N, vector<int>(LOG, 0));
for (int i{}; i < N; i++)
m[i][0] = lcp[i];
for (int k = 1; k < LOG; k++)
{
for (int i{}; i + (1 << k) - 1 < N; i++)
m[i][k] = min(m[i][k - 1], m[i + (1 << (k - 1))][k - 1]);
}
}
int query(int L, int R) // 0-based
{
if (L == R)
return N - L - 1;
L = pos[L], R = pos[R];
if (L > R)
swap(L, R);
R--;
int len = R - L + 1;
int k = 31 - clz(len);
return min(m[L][k], m[R - (1 << k) + 1][k]);
}
}
using namespace SuffixArray;
bool compare(const pair<int, int> &P1, const pair<int, int> &P2)
{
const auto &[i, j] = P1;
const auto &[k, l] = P2;
int len1 = j - i + 1, len2 = l - k + 1;
int LCP = query(i, k);
if (LCP >= min(len1, len2))
{
if (len1 == len2) // The two strings are equal
{
if (i != k)
return i < k;
return j <= l;
}
return len1 < len2;
}
return S[i + LCP] <= S[k + LCP];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("Output.txt", "w", stdout
); #endif //! ONLINE_JUDGE
int t = 1;
ll N, Q;
// cin >> t;
while (t--)
{
cin >> S;
S.push_back(' ');
buildSA();
buildLCP();
cin >> Q;
vector<pair<int, int>> vc;
while (Q--)
{
int L, R;
cin >> L >> R;
vc.push_back({--L, --R});
}
sort(vc.begin(), vc.end(), compare);
for (auto &[l, r] : vc)
cout << ++l << " " << ++r << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nIGludAojZGVmaW5lIGVuZGwgIlxuIgoKbGwgY2x6KGxsIE4pCnsKCWxsIGlkeHt9OwoJZm9yIChpbnQgaSA9IDA7IGkgPCAzMjsgaSsrKQoJewoJCWlmIChOICYgKDFMTCA8PCBpKSkKCQkJaWR4ID0gaTsKCX0KCXJldHVybiAzMSAtIGlkeDsKfQoKbmFtZXNwYWNlIFN1ZmZpeEFycmF5CnsKCWNvbnN0IGludCBtYXhOID0gNGU1ICsgMTA7CglzdHJpbmcgUzsKCWxsIE4sIGdhcDsKCWludCBTQVttYXhOXSwgcG9zW21heE5dLCB0bXBbbWF4Tl07Cgl2ZWN0b3I8aW50PiBsY3AobWF4Tik7Cgl2ZWN0b3I8dmVjdG9yPGludD4+IG07CgoJYm9vbCBzdWZDbXAoaW50IGksIGludCBqKQoJewoJCWlmIChwb3NbaV0gIT0gcG9zW2pdKQoJCQlyZXR1cm4gcG9zW2ldIDwgcG9zW2pdOwoJCWkgKz0gZ2FwOwoJCWogKz0gZ2FwOwoJCXJldHVybiAoaSA8IE4gJiYgaiA8IE4pID8gcG9zW2ldIDwgcG9zW2pdIDogaSA+IGo7Cgl9CgoJdm9pZCBidWlsZFNBKCkKCXsKCQlOID0gUy5zaXplKCk7CgkJZm9yIChpbnQgaXt9OyBpIDwgTjsgaSsrKQoJCQlTQVtpXSA9IGksCgkJCXBvc1tpXSA9IFNbaV07CgkJZm9yIChnYXAgPSAxOzsgZ2FwICo9IDIpCgkJewoJCQlzb3J0KFNBLCBTQSArIE4sIHN1ZkNtcCk7CgkJCWZvciAoaW50IGl7fTsgaSA8IE4gLSAxOyBpKyspCgkJCQl0bXBbaSArIDFdID0gdG1wW2ldICsgc3VmQ21wKFNBW2ldLCBTQVtpICsgMV0pOwoJCQlmb3IgKGludCBpe307IGkgPCBOOyBpKyspCgkJCQlwb3NbU0FbaV1dID0gdG1wW2ldOwoJCQlpZiAodG1wW04gLSAxXSA9PSBOIC0gMSkKCQkJCWJyZWFrOwoJCX0KCX0KCgl2b2lkIGJ1aWxkTENQKCkKCXsKCQlmb3IgKGludCBpID0gMCwgayA9IDA7IGkgPCBOOyArK2kpCgkJewoJCQlpZiAocG9zW2ldICE9IE4gLSAxKQoJCQl7CgkJCQlmb3IgKGludCBqID0gU0FbcG9zW2ldICsgMV07IFNbaSArIGtdID09IFNbaiArIGtdOykKCQkJCQkrK2s7CgkJCQlsY3BbcG9zW2ldXSA9IGs7CgkJCQlpZiAoaykKCQkJCQktLWs7CgkJCX0KCQl9CgkJaW50IExPRyA9IGNlaWwobG9nMihOKSkgKyAxOwoJCW0ucmVzaXplKE4sIHZlY3RvcjxpbnQ+KExPRywgMCkpOwoJCWZvciAoaW50IGl7fTsgaSA8IE47IGkrKykKCQkJbVtpXVswXSA9IGxjcFtpXTsKCQlmb3IgKGludCBrID0gMTsgayA8IExPRzsgaysrKQoJCXsKCQkJZm9yIChpbnQgaXt9OyBpICsgKDEgPDwgaykgLSAxIDwgTjsgaSsrKQoJCQkJbVtpXVtrXSA9IG1pbihtW2ldW2sgLSAxXSwgbVtpICsgKDEgPDwgKGsgLSAxKSldW2sgLSAxXSk7CgkJfQoJfQoJaW50IHF1ZXJ5KGludCBMLCBpbnQgUikgLy8gMC1iYXNlZAoJewoJCWlmIChMID09IFIpCgkJCXJldHVybiBOIC0gTCAtIDE7CgkJTCA9IHBvc1tMXSwgUiA9IHBvc1tSXTsKCQlpZiAoTCA+IFIpCgkJCXN3YXAoTCwgUik7CgkJUi0tOwoJCWludCBsZW4gPSBSIC0gTCArIDE7CgkJYXNzZXJ0KGxlbiA+IDApOwoJCWludCBrID0gMzEgLSBjbHoobGVuKTsKCQlyZXR1cm4gbWluKG1bTF1ba10sIG1bUiAtICgxIDw8IGspICsgMV1ba10pOwoJfQp9CnVzaW5nIG5hbWVzcGFjZSBTdWZmaXhBcnJheTsKCmJvb2wgY29tcGFyZShjb25zdCBwYWlyPGludCwgaW50PiAmUDEsIGNvbnN0IHBhaXI8aW50LCBpbnQ+ICZQMikKewoJY29uc3QgYXV0byAmW2ksIGpdID0gUDE7Cgljb25zdCBhdXRvICZbaywgbF0gPSBQMjsKCWludCBsZW4xID0gaiAtIGkgKyAxLCBsZW4yID0gbCAtIGsgKyAxOwoKCWludCBMQ1AgPSBxdWVyeShpLCBrKTsKCWlmIChMQ1AgPj0gbWluKGxlbjEsIGxlbjIpKQoJewoJCWlmIChsZW4xID09IGxlbjIpIC8vIFRoZSB0d28gc3RyaW5ncyBhcmUgZXF1YWwKCQl7CgkJCWlmIChpICE9IGspCgkJCQlyZXR1cm4gaSA8IGs7CgkJCXJldHVybiBqIDw9IGw7CgkJfQoJCXJldHVybiBsZW4xIDwgbGVuMjsKCX0KCXJldHVybiBTW2kgKyBMQ1BdIDw9IFNbayArIExDUF07Cn0KCmludCBtYWluKCkKewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKG51bGxwdHIpOwojaWZuZGVmIE9OTElORV9KVURHRQoJZnJlb3BlbigiaW5wdXQudHh0IiwgInIiLCBzdGRpbik7CglmcmVvcGVuKCJPdXRwdXQudHh0IiwgInciLCBzdGRvdXQpOwojZW5kaWYgLy8hIE9OTElORV9KVURHRQoJaW50IHQgPSAxOwoJbGwgTiwgUTsKCS8vIGNpbiA+PiB0OwoJd2hpbGUgKHQtLSkKCXsKCQljaW4gPj4gUzsKCQlTLnB1c2hfYmFjaygnICcpOwoJCWJ1aWxkU0EoKTsKCQlidWlsZExDUCgpOwoKCQljaW4gPj4gUTsKCQl2ZWN0b3I8cGFpcjxpbnQsIGludD4+IHZjOwoJCXdoaWxlIChRLS0pCgkJewoJCQlpbnQgTCwgUjsKCQkJY2luID4+IEwgPj4gUjsKCQkJdmMucHVzaF9iYWNrKHstLUwsIC0tUn0pOwoJCX0KCQlzb3J0KHZjLmJlZ2luKCksIHZjLmVuZCgpLCBjb21wYXJlKTsKCQlmb3IgKGF1dG8gJltsLCByXSA6IHZjKQoJCQljb3V0IDw8ICsrbCA8PCAiICIgPDwgKytyIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==