好忙，不过题还是得补，欠了好多了已经。
J Suffix Automaton
场上没看见第一关键字是长度，还跟队友反复确认是不是本质不同，还剩17分钟rush了一个，结果发现样例都过不去，成功没写完这个F。
如果按照第一关键字为长度排序的话依然可以二分出答案的长度。后缀排序之后一个后缀会贡献 \([ht_i + 1, n - sa_i + 1]\) 区间内长度的串，所以我们可以将询问离线下来使用一个权值线段树来查询 Kth，需要注意的是查询出来的那个位置是 后缀排序后 最靠前的那个位置，而不是 原序列 中最靠前的那个位置。如果我们得到了后缀排序后的那个位置 \(p\) ，相当于还需要维护 \(ht\) 长度 \(\geq\) 这个长度的 \(p\) 前后的一段的 \(sa\) 数组中的最小值，这一步依然可以离线，按照 \(ht\) 从大到小合并相邻的位置，顺便维护一下连通块中的 \(sa\) 最小值即可，并查集可做。
这么看下来后缀数组做挺麻烦的，相当于将一个题拆成了两个题做。
另一件比较无奈的事情是，如果暴力开主席树在线做的话空间是有点开不下的……
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;
#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif
const int N = 1e6 + 5;
const ll P = 998244353LL;
int n, qn, trueQn;
int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];
char str[N];
int ufs[N], mn[N], ans[N][2];
ll cntSum[N];
struct InsNode {
int id;
ll v;
/* v = 1: ins */
/* v = -1: del */
};
vector <InsNode> vec[N];
struct QueryNode1 {
int id, len;
ll k;
};
vector <QueryNode1> q1[N];
struct QueryNode2 {
int id, len, pos;
};
vector <QueryNode2> q2[N];
inline bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
inline void saInit() {
memset(cnt, 0, sizeof(cnt));
int m = 200, p;
for (int i = 1; i <= n; i++) ++cnt[rk[i] = str[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 w = 1; w < n; w <<= 1, m = p) {
p = 0;
for (int i = n; i > n - w; i--) id[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
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];
memcpy(oldrk, rk, sizeof(rk));
p = 0;
for (int i = 1; i <= n; i++)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
for (int i = 1, k = 0; i <= n; i++) {
if (k) --k;
for (; str[i + k] == str[sa[rk[i] - 1] + k]; ++k);
ht[rk[i]] = k;
}
}
namespace SegT {
ll s[N << 2];
#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)
inline void up(int p) {
s[p] = s[lc] + s[rc];
}
void modify(int p, int l, int r, int x, ll v) {
if (l == r) {
s[p] += v;
return;
}
if (x <= mid) modify(lc, l, mid, x, v);
else modify(rc, mid + 1, r, x, v);
up(p);
}
int query(int p, int l, int r, ll k) {
if (l == r) return l;
ll cur = s[lc];
if (k > cur) return query(rc, mid + 1, r, k - cur);
else return query(lc, l, mid, k);
}
#undef mid
} using namespace SegT;
inline void solve1() {
for (int i = 1; i <= n; i++) {
for (auto insNode : vec[i]) {
modify(1, 1, n, insNode.id, insNode.v);
}
for (auto qryNode : q1[i]) {
int res = query(1, 1, n, qryNode.k);
// printf("%d %d\n", qryNode.id, sa[res]);
q2[qryNode.len].emplace_back((QueryNode2) {qryNode.id, qryNode.len, res});
}
}
}
int get(int x) {
return ufs[x] == x ? x : ufs[x] = get(ufs[x]);
}
inline void merge(int x, int y) {
int fx = get(x), fy = get(y);
if (fx == fy) return;
ufs[fx] = fy;
mn[fy] = min(mn[fy], mn[fx]);
}
vector <int> htNode[N];
inline void solve2() {
for (int i = 1; i <= n; i++) {
ufs[i] = i;
mn[i] = sa[i];
}
for (int i = 2; i <= n; i++) htNode[ht[i]].emplace_back(i);
for (int i = n; i >= 1; i--) {
for (auto curHtNode : htNode[i]) {
merge(curHtNode - 1, curHtNode);
}
for (auto qryNode : q2[i]) {
int res = mn[get(qryNode.pos)];
ans[qryNode.id][0] = res, ans[qryNode.id][1] = res + qryNode.len - 1;
}
}
}
#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif
int main() {
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
clock_t st_clock = clock();
#endif
scanf("%s", str + 1);
n = strlen(str + 1);
saInit();
// assert(ht[1] == 0);
ll tot = 0;
for (int i = 1; i <= n; i++) {
tot += n + 1 - ht[i] - sa[i];
++cntSum[ht[i] + 1];
--cntSum[n - sa[i] + 1 + 1];
vec[ht[i] + 1].emplace_back((InsNode) {i, 1});
vec[n - sa[i] + 1 + 1].emplace_back((InsNode) {i, -1});
// printf("%d %d\n", ht[i] + 1, n - sa[i] + 1);
}
for (int i = 1; i <= n; i++) cntSum[i] += cntSum[i - 1];
for (int i = 1; i <= n; i++) cntSum[i] += cntSum[i - 1];
// for (int i = 1; i <= n; i++)
// printf("%lld%c", cntSum[i], " \n"[i == n]);
// printf("%lld\n", tot);
scanf("%d", &qn);
trueQn = 0;
for (int i = 1; i <= qn; i++) {
ll k;
scanf("%lld", &k);
if (k > tot) {
ans[i][0] = ans[i][1] = -1;
} else if (k == tot) {
ans[i][0] = 1, ans[i][1] = n;
} else {
++trueQn;
int l = 0, r = n, mid, res = -1;
for (; l <= r; ) {
mid = (l + r) / 2;
if (cntSum[mid] < k) l = mid + 1, res = mid;
else r = mid - 1;
}
assert(res < n && res >= 0);
q1[res + 1].emplace_back((QueryNode1) {i, res + 1, k - cntSum[res]});
}
}
solve1();
solve2();
for (int i = 1; i <= qn; i++)
printf("%d %d\n", ans[i][0], ans[i][1]);
#ifndef ONLINE_JUDGE
clock_t ed_clock = clock();
printf("time = %f ms\n", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
printf("memory = %.2f MB\n", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
return 0;
}