1. 题目

传送门=￣ω￣=

2. 题解

一个模板题我做了这么这么久 T^T

而且出题人很有趣，数据不知道怎么搞的，不用二分直接暴力都能过（而且 $Rank1$就是暴力而且这个 $Rank1$就是 FKL）

但是他却以非常小的概率卡掉了我的一个细节（等下代码会说）

。。。MMP。。。

首先求出 $SA$数组和 $Height$数组

对于某个子串，它一定是某后缀的前缀

对于排名为 $i$的后缀，它有 $n – SA[i] + 1 – Height[i]$个前缀是在排名比它靠前的后缀中没出现过的

所以它对子串个数的贡献就是 $n – SA[i] + 1 – Height[i]$

这样我们就能找到排名为 $k$的子串在 $SA$中第一次出现的位置了

这样我们等于确定了这个字符串的 “内容”

但是它的位置还可能可以更靠前（$SA$中靠前的不一定在原串中靠前）

所以我们查找该子串在 $SA$中可能出现的区间（区间开头就是上面那个位置，区间结尾再用二分查找一下）

需要满足区间的 $Height$的最小值大于等于子串长度

然后再在 $SA$上求这个区间的最小值，便是第 $k$小子串的开头位置了

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define LGS (17)

using namespace std;

typedef long long LL;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

char s[NS];

int n, SA[NS], x[NS << 1], y[NS << 1], Hi[NS];

LL T[NS];

void Rsort(int p)
{
    for (int i = 1; i <= p; i += 1) T[i] = 0;
    for (int i = 1; i <= n; i += 1) T[x[y[i]]]++;
    for (int i = 2; i <= p; i += 1) T[i] += T[i - 1];
    for (int i = n; i >= 1; i -= 1) SA[T[x[y[i]]]--] = y[i];
}

void GetSA()
{
    for (int i = 1; i <= n; i += 1) x[i] = s[i] - 'a' + 1, y[i] = i;
    int p = 26; Rsort(p);
    for (int l = 1, q = 0; q < n; l <<= 1, p = q)
    {
        q = 0;
        for (int i = n - l + 1; i <= n; i += 1) y[++q] = i;
        for (int i = 1; i <= n; i += 1) if (SA[i] > l) y[++q] = SA[i] - l;
        Rsort(p), swap(x, y), q = x[SA[1]] = 1;
        for (int i = 2; i <= n; i += 1)
            if (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + l] == y[SA[i - 1] + l])
                x[SA[i]] = q;
            else x[SA[i]] = ++q;
    }
}

void GetHi()
{
    for (int i = 1, lcp = 0, j; i <= n; i += 1)
    {
        if (lcp) lcp--;
        j = SA[x[i] - 1];
        while (s[i + lcp] == s[j + lcp]) lcp++;
        Hi[x[i]] = lcp;
    }
}

struct RMQ
{
    int d[NS], st[NS][LGS + 1], lg[NS];
    int& operator [] (const int a) {return d[a];}
    void Build()
    {
        for (int i = 2; i <= n; i += 1)
            if (i == (1 << (lg[i - 1] + 1))) lg[i] = lg[i - 1] + 1;
            else lg[i] = lg[i - 1];
        for (int i = 1; i <= n; i += 1) st[i][0] = d[i];
        for (int l = 1; (1 << l) <= n; l += 1)
            for (int i = 1; i + (1 << l) - 1 <= n; i += 1)
                st[i][l] = min(st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
    }
    int Query(int l, int r)
    {
        int k = lg[r - l + 1];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
} r1, r2;

int main(int argc, char const* argv[])
{
    while (~scanf("%s", s + 1))
    {
        n = strlen(s + 1), GetSA(), GetHi(), Hi[n + 1] = 0;
        for (int i = 1; i <= n; i += 1)
            r1[i] = Hi[i], r2[i] = SA[i], T[i] = T[i - 1] + n - SA[i] + 1 - Hi[i];
        r1.Build(), r2.Build();
        int q, l, r, mid, x1 = 0, x2 = 0, p, len; LL k; IN(q);
        while (q--)
        {
            IN(k), k = (k ^ x1 ^ x2) + 1;
            if (k > T[n]) x1 = x2 = 0;
            else
            {
                p = lower_bound(T + 1, T + 1 + n, k) - T;
                len = k - T[p - 1] + Hi[p], l = p + 1, r = n;
                while (l < r)
                    if (mid = (l + r + 1) >> 1, r1.Query(p + 1, mid) >= len) l = mid;
                    else r = mid - 1;
                if (Hi[l] < len) l--; // 当 p = n 时，如果把 l 写成 r 有可能挂，因为初始 l = r + 1
                x1 = r2.Query(p, l), x2 = x1 + len - 1;
            }
            printf("%d %d\n", x1, x2);
        }
    }
    return 0;
}