vector<int> lcp, ind, sr, ps;
map<int, vector<int>> ids;

vector<int> calc_lcp(string &val, vector<int> &c, vector<int> &p) {
    int n = len(val);
    int current_lcp = 0;
    vector<int> lcp(n);
    for (int i = 0; i < n; i++) {
        if (c[i] == n - 1)
            continue;
        int nxt = p[c[i] + 1];
        while (max(i, nxt) + current_lcp < n && val[i + current_lcp] == val[nxt + current_lcp])
            current_lcp++;
        lcp[c[i]] = current_lcp;
        current_lcp = max(0ll, current_lcp - 1);
    }
    return lcp;
}

vector<int> suffix_array(string &s) {
    s.push_back(0);
    int n = len(s),cnt = 0, cls = 0;
    vector<int> c(n), p(n);

    map<int, vector<int>> t;
    for (int i = 0; i < n; i++)
        t[s[i]].push_back(i);

    for (auto &x : t) {
        for (int u : x.y)
            c[u] = cls, p[cnt++] = u;
        cls++;
    }

    for (int l = 1; cls < n; l++) {
        vector<vector<int>> a(cls);
        vector<int> _c(n);
        int d = (1 << l) / 2;
        int _cls = cnt = 0;

        for (int i = 0; i < n; i++) {
            int k = (p[i] - d + n) % n;
            a[c[k]].push_back(k);
        }

        for (int i = 0; i < cls; i++) {
            for (int j = 0; j < len(a[i]); j++) {
                if (j == 0 || c[(a[i][j] + d) % n] != c[(a[i][j - 1] + d) % n])
                    _cls++;
                _c[a[i][j]] = _cls - 1;
                p[cnt++] = a[i][j];
            }
        }

        c = _c;
        cls = _cls;
    }

    lcp = calc_lcp(s, c, p);
    return vector<int>(p.begin() + 1, p.end());
}