#include <bits/stdc++.h>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef
tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const int nmax = 1e6 + 100;
const int inf = 1e9;
const int rmax = 22;
int sparse[rmax][nmax];
int deg[nmax];
int p[nmax], pos[nmax], lcp[nmax];
int cnt[nmax];
int c[nmax];
int cn[nmax], pn[nmax];
void suffixArray(const string& s) {
int n = sz(s);
for (int i = 0; i < n; ++i) {
++cnt[s[i]];
}
for (int i = 1; i < nmax; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
p[--cnt[s[i]]] = i;
}
c[p[0]] = 0;
for (int i = 1; i < n; ++i) {
c[p[i]] = c[p[i - 1]];
if (s[p[i]] != s[p[i - 1]]) {
++c[p[i]];
}
}
int len = 1;
for (int j = 0; len < n; ++j, len <<= 1) {
for (int i = 0; i < n; ++i) {
pn[i] = p[i] - len;
if (pn[i] < 0) {
pn[i] += n;
}
}
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i) {
++cnt[c[i]];
}
for (int i = 1; i < n; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
p[--cnt[c[pn[i]]]] = pn[i];
}
cn[p[0]] = 0;
for (int i = 1; i < n; ++i) {
cn[p[i]] = cn[p[i - 1]];
if (c[p[i]] != c[p[i - 1]]) {
++cn[p[i]];
continue;
}
int x = p[i] + len;
if (x >= n) {
x -= n;
}
int y = p[i - 1] + len;
if (y >= n) {
y -= n;
}
if (c[x] != c[y]) {
++cn[p[i]];
}
}
memcpy(c, cn, sizeof(c));
}
for (int i = 0; i < n; ++i) {
pos[p[i]] = i;
}
int k = 0;
for (int i = 0; i < n; ++i) {
if (pos[i] == n - 1) {
k = 0;
continue;
}
k = max(k - 1, 0);
int j = p[pos[i] + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
++k;
}
lcp[pos[i]] = k;
}
}
struct query {
ll k;
int id;
bool operator<(const query& other) const {
return k < other.k;
}
};
void rem(ordered_set& s, int x) {
pii pp = {x, inf};
ordered_set::iterator it = s.upper_bound(pp);
--it;
int l = it->first, r = it->second;
assert(l <= x && x <= r);
s.erase(it);
if (l <= x - 1) {
s.insert({l, x - 1});
}
if (x + 1 <= r) {
s.insert({x + 1, r});
}
}
void split(ordered_set& s, int z) {
pii pp = {z, inf};
ordered_set::iterator it = s.upper_bound(pp);
//cout << "!" << it->first << " " << it->second << endl;
--it;
int l = it->first, r = it->second;
assert(l <= z && z + 1 <= r);
s.erase(it);
s.insert({l, z});
s.insert({z + 1, r});
}
int getMax(int l, int r) {
int k = deg[r - l + 1];
return max(sparse[k][l], sparse[k][r - (1 << k) + 1]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//ifstream cin("input.txt");
deg[0] = -1;
for (int i = 1; i < nmax; ++i) {
deg[i] = deg[i - 1];
if (!(i & (i - 1))) {
++deg[i];
}
}
string s;
cin >> s;
s += "#";
int n = sz(s);
suffixArray(s);
int q;
cin >> q;
vector<query> queries(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].k;
queries[i].id = i;
}
sort(all(queries));
ordered_set setik;
int l = 1;
for (int r = 2; r < n; ++r) {
if (s[p[r]] != s[p[l]]) {
setik.insert({l, r - 1});
l = r;
}
}
setik.insert({l, n - 1});
int curLen = 1;
ll skipped = 0;
vector<pii> ans(q, {-1, -1});
vector<vector<int> > equalLCP(n + 1);
for (int i = 0; i < n - 1; ++i) {
equalLCP[lcp[i]].pb(i);
}
/*for (int i = 0; i < n - 1; ++i) {
cout << lcp[i] << "\n";
}
return 0;*/
/*for (pii pp : setik) {
cout << pp.first << " " << pp.second << endl;
}
return 0;*/
for (int i = 0; i < n; ++i) {
sparse[0][i] = n - p[i];
}
for (int r = 0; r + 1 < rmax; ++r) {
for (int i = 0; i < n; ++i) {
int j = min(n - 1, i + (1 << r));
sparse[r + 1][i] = max(sparse[r][i], sparse[r][j]);
}
}
for (query Q : queries) {
Q.k -= skipped;
bool bad = false;
while (Q.k > sz(setik)) {
if (curLen == n) {
bad = true;
break;
}
skipped += sz(setik);
Q.k -= sz(setik);
int x = pos[n - curLen - 1];
rem(setik, x);
for (int z : equalLCP[curLen]) {
//cout << "!" << z << endl;
int len = n - p[z] - 1;
if (len <= curLen) {
continue;
}
len = n - p[z + 1] - 1;
if (len <= curLen) {
continue;
}
split(setik, z);
}
++curLen;
}
if (bad) {
continue;
}
// pp - kth pair in setik
pii pp = *(setik.find_by_order(Q.k - 1));
int l = pp.first, r = pp.second;
//cout << "!" << pp.first << " " << pp.second << endl;
int len = getMax(l, r);
ans[Q.id] = {n - len + 1, n - len + 1 + curLen - 1};
//cout << Q.id << " " << curLen << endl;
//cout << "!" << skipped << endl;
}
for (int i = 0; i < q; ++i) {
cout << ans[i].first << " " << ans[i].second << "\n";
}
}