#include "bits/stdc++.h"

#pragma GCC optimize("Ofast")
#pragma GCC targetr("avx2")
#define int long long
using namespace std;

using ll = long long;
using pii = pair<int, int>;

using vi = vector<int>;
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); i++)

struct SuffixArray {
	vi sa, lcp;
	SuffixArray(string &s, int lim = 256) {
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s) + 1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1LL, j * 2), lim = p) {
			p = j, iota(all(y),  n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i, 1, n) a = sa[i - 1], b = sa[i], x[b] = 
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1: p++;			
		}
		rep(i, 1, n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
				s[i + k] == s[j + k] && max(i + k, j + k) < s.size(); k++);
	}
};

struct DSU {
	int n;
	vector<int> dsu;
	vector<int> mn, mx;
	DSU(int _n) {
		n = _n;
		dsu.resize(n);
		mn.resize(n), mx.resize(n);
		iota(dsu.begin(), dsu.end(), 0);
		iota(mn.begin(), mn.end(), 0);
		iota(mx.begin(), mx.end(), 0);

	}

	int find(int x) {
		if (dsu[x] == x) return x;
		else return dsu[x] = find(dsu[x]);
	}

	void uni(int x, int y) {
		x = find(x);
		y = find(y);

		// cout << "Uni: " << x << " " << y << endl;
		if (x == y) return;

		dsu[y] = x;
		mx[x] = max(mx[x], mx[y]);
		mn[x] = min(mn[x], mn[y]);
	}
};

const int MAXN = 500005;

struct RankQuery{
	int l, r, k, add;
};

#define int long long
int s2(int l, int r){
	return (l + r) * (r - l + 1) / 2;
}

struct TREE{
#define mid ((l + r) >> 1)
#define lson l, mid
#define rson mid + 1, r

	struct P {
		int w, ls, rs;
	} tr[MAXN * 20];
	int sz = 1;
	TREE() { tr[0] = {0, 0, 0}; }
	int N(int w, int ls, int rs){
		tr[sz] = {w, ls, rs};
		return sz++;
	}
	int ins(int tt, int l, int r, int x){
		if(x < l || r < x) return tt;
		const P& t = tr[tt];
		if(l == r) return N(t.w + 1, 0, 0);
		return N(t.w + 1, ins(t.ls, lson, x), ins(t.rs, rson, x));
	}
	int query(int pp, int qq, int l, int r, int k) {
		if(l == r) return l;
		const P& p = tr[pp], &q = tr[qq];
		int w = tr[q.ls].w - tr[p.ls].w;
		if(k <= w) return query(p.ls, q.ls, lson, k);
		else return query(p.rs, q.rs, rson, k - w);
	}
} ST;

int rt[MAXN];

void solve(int TC) {
	string s;
	cin >> s;

	SuffixArray SA(s);
	int n = s.size();

	DSU dsu(n + 1);

	struct Node {
		int L, R;
		int mnlen, mxlen;
	};

	vector<vector<int>> g;
	vector<Node> nde;

	vector<int> nodepnt(n + 1, -1);	
	vector<vector<int>> merge(MAXN);

	for (int i = 1; i <= n; i++) {
		// cout << "SA: " << SA.sa[i] << " lcp: " << SA.lcp[i] << endl;
		if (i > 1) {
			merge[SA.lcp[i]].push_back(i - 1);
		}

		int len = n - SA.sa[i];
		nodepnt[i] = nde.size();
		nde.push_back({i, i, len + 1, len});
		g.push_back({});
	}

	for (int i = MAXN - 1; i >= 0; i--) {
		int sz = (int)merge[i].size();
		for (int j = 0; j < sz; j++) {
			vector<int> vec;

			int x = merge[i][j], y = x + 1;

			// cout << "!" << x << " " << y << endl;
			x = dsu.find(x), y = dsu.find(y);
			// cout << "#" << x << " " << y << endl;
		
			vec.push_back(nodepnt[x]);
			vec.push_back(nodepnt[y]);
			dsu.uni(x, y);

			while (j + 1 < sz && merge[i][j + 1] == dsu.mx[x]) {
				++j;
				y = merge[i][j] + 1;
				y = dsu.find(y);
				vec.push_back(nodepnt[y]);

				dsu.uni(x, y);
			}

			int id = nde.size();
			nodepnt[x] = id;
			nde.push_back({dsu.mn[x], dsu.mx[x], i, i});
			g.push_back({});
			for (auto ch: vec) {
				// cout << "@" << i << " : " << dsu.mn[x] << " " << dsu.mx[x] << " " << ch << endl;
				nde[ch].mnlen = i + 1;
				g[id].push_back(ch);
			}
		}
	}

	int S = (int)nde.size() - 1;

	int q; cin >> q;
	vector<pair<int, int>> Q; 
	for(int i = 0; i < q; i++){
		int v; cin >> v;
		Q.push_back({v, i});
	}
	sort(Q.begin(), Q.end());
	vector<RankQuery> RQ(q);

	int cnt = 0, qi = 0;
	auto dfs = [&](auto &&dfs, int u, int p) -> void {
		int len = nde[u].R - nde[u].L + 1;
		int sz = len * s2(nde[u].mnlen, nde[u].mxlen);
		while(qi < q && Q[qi].first <= cnt + sz){
			auto [v, i] = Q[qi];
			int x = Q[qi].first - cnt - 1;

			int y = 0;
			{
				int yl = nde[u].mnlen, yr = nde[u].mxlen;
				while(yl != yr){
					int ym = (yl + yr) / 2;
					if(x < len * s2(nde[u].mnlen, ym))
						yr = ym;
					else
					 	yl = ym + 1;
				}
				y = yl; x -= len * s2(nde[u].mnlen, y - 1);
			}
			RQ[i] = RankQuery{nde[u].L, nde[u].R, x / (y - nde[u].mnlen + 1), x % (y - nde[u].mnlen + 1)};
			++qi;
		}
		cnt += sz;
		// cout << "Node " << u << " >>>   L: " << nde[u].L << " R: " << nde[u].R << " mnlen: " << nde[u].mnlen << " mxlen: " << nde[u].mxlen << endl;
		// cout << "Current count = " << cnt << endl;
		for (auto v: g[u]) {
			if (v == p) continue;
			// cout << "Edge: " << u << " -> " << v << endl;
			dfs(dfs, v, u);
		}
	};
	dfs(dfs, S, -1);

	for(int i = 1; i <= n; i++){
		rt[i] = ST.ins(rt[i - 1], 0, n, SA.sa[i]);
	}

	// for(int i = 1; i <= n; i++){
	// 	cout << SA.sa[i] << ' ';
	// }
	// cout << '\n';
	for(int i = 0; i < q; i++){
		auto [l, r, k, add] = RQ[i];
		int ans = add + 1 + ST.query(rt[l - 1], rt[r], 0, n, k + 1);
		cout << ans << '\n';
		// cout << l << ' ' << r << ' ' << k + 1 << ' ' << add << endl;
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}