#include <bits/stdc++.h>
#include <bits/extc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e6 + 10;

int q, n;
char s[N];
int sa[N], rk[N << 1], ork[N << 1], px[N], id[N], ht[N], cnt[N], m;

priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > ques;

using namespace __gnu_cxx;
using namespace __gnu_pbds;

ll tot;

tree < pii, null_type, less < pii >, rb_tree_tag, tree_order_statistics_node_update > t;

vec lim[N], del[N];
pii ans[N];

void ins(int l, int r) { if(l <= r) t.insert({ l, r }); }

void cut(int x) {
	auto it = t.upper_bound(pii{ x, n + 1 });
	if(it == t.begin()) return; it--;
	int l, r; tie(l, r) = *it;
	if(l <= x && x <= r) {
		t.erase(it);
		ins(l, x - 1), ins(x, r);
	}
}

void rem(int x) {
	auto it = t.upper_bound(pii{ x, n + 1 });
	if(it == t.begin()) return; it--;
	int l, r; tie(l, r) = *it;
	if(l <= x && x <= r) {
		t.erase(it);
	//	cerr << " ! REM " << x << " " << l << " " << r << endl;
		ins(l, x - 1), ins(x + 1, r);
	}
}

int st[21][N], lg[N];

int qmin(int l, int r) {
	int k = lg[r - l + 1];
	return min(st[k][l], st[k][r - (1 << k) + 1]);
	int x = sa[l]; rep(i, l, r) chkmin(x, sa[i]);
	return x;
}

int get(int rk) {
	//cerr << rk << " " << t.size() << endl;
	auto it = t.find_by_order(rk - 1); assert(it != t.end());
	int l, r; tie(l, r) = *it;
	return qmin(l, r);
}

int main() {
#ifdef YJR_2333_TEST
	freopen("1.in", "r", stdin);
#endif
	scanf("%s",s+1); n = strlen(s+1); m = 300;
	for(int i = 1;i <= n;i++) ++cnt[rk[i]=s[i]];
	for(int i = 1;i <= m;i++) cnt[i] += cnt[i-1];
	for(int i = n;i >= 1;i--) sa[cnt[rk[i]]--] = i;
	for(int h = 1,p;h <= n;h<<=1,m = p){
		p = 0;for(int i = n;i > n-h;i--) id[++p] = i;
		for(int i = 1;i <= n;i++) if(sa[i] > h) id[++p] = sa[i] - h;
		for(int i = 1;i <= m;i++) cnt[i] = 0;
		for(int i = 1;i <= n;i++) ++cnt[px[i] = rk[id[i]]];
		for(int i = 1;i <= m;i++) cnt[i] += cnt[i-1];
		for(int i = n;i >= 1;i--) sa[cnt[px[i]]--]=id[i];
		for(int i = 1;i <= n;i++) ork[i] = rk[i];
		p = 0;
		for(int i = 1;i <= n;i++)
			rk[sa[i]] = (ork[sa[i-1]] == ork[sa[i]] && ork[sa[i-1] + h] == ork[sa[i] + h]) ? p : ++p;
	}
	rep(i, 1, n) st[0][i] = sa[i];
	rep(i, 2, n) lg[i] = lg[i >> 1] + 1;
	rep(i, 1, 20) rep(j, 1, n) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i)]);
	int j = 0;
	rep(i, 1, n) {
		if(rk[i] == 0) continue;
		if(j > 0) j--;
		while(s[i + j] == s[sa[rk[i] - 1] + j]) j++;
		ht[rk[i]] = j;
		lim[j + 1].eb(rk[i]);
	}
	rep(i, 1, n) del[n - i + 1].eb(rk[i]);
	t.insert({ 1, n });
	q = in; rep(i, 1, q) { ll k = lin; ques.ep(k, i); }
	/*
	rep(i, 1, n) cerr << sa[i] << " "; cerr << endl;
	rep(i, 1, n) cerr << ht[i] << " "; cerr << endl;
	*/
	rep(len, 1, n) {
		//lim
		for(auto v : lim[len]) cut(v);
		//cerr << "!" << len << endl;
		//for(auto v : t) cerr << v.fi << " " << v.se << endl;
		ll cur = t.size();
		while(ques.size() && ques.top().fi - tot <= cur) {
			int x = ques.top().se; ll ret = ques.top().fi; ques.pop();
			ans[x].fi = get(ret - tot), ans[x].se = ans[x].fi + len - 1;
		} tot += cur;
		//del
		for(auto v : del[len]) rem(v);
	}
	rep(i, 1, q) {
		if(ans[i].fi == 0) ans[i].fi = ans[i].se = -1;
		printf("%d %d\n", ans[i].fi, ans[i].se);
	}
	return 0;
}