const int MAX = 100 * 1000 + 47;
const int LEN = 18; // ceil(log(MAX))
const int ALP = 128; // Alphabet size

int CL[LEN][MAX];
int P[LEN][MAX];
int CNT[MAX];
int POS[MAX];
int lastLev = -1; // P[lastLev] - final array

void build(const string& s)
{
    int n = SZ(s);
    FOR(i, 0, n)
    {
        CNT[s[i]]++;
    }

    int sum = 0;
    FOR(i, 0, ALP)
    {
        POS[i] = sum;
        sum += CNT[i];
    }

    FOR(i, 0, n)
    {
        P[0][POS[s[i]]++] = i;
    }

    CL[0][P[0][0]] = 0;
    FOR(i, 1, n)
    {
        int cur = P[0][i];
        int prev = P[0][i - 1];
        CL[0][cur] = CL[0][prev];
        if (s[cur] != s[prev]) CL[0][cur]++;
    }

    FOR(it, 1, LEN)
    {
        if ((1 << (it - 1)) >= n)
        {
            lastLev = it - 1;
            break;
        }

        FILL(CNT, 0);
        FOR(i, 0, n)
        {
            CNT[CL[it - 1][i]]++;
        }

        int sum = 0;
        FOR(i, 0, n)
        {
            POS[i] = sum;
            sum += CNT[i];
        }

        FOR(i, 0, n)
        {
            int x = P[it - 1][i] - (1 << (it - 1));
            if (x < 0) x += n;

            int cl = CL[it - 1][x];
            P[it][POS[cl]++] = x;
        }

        CL[it][P[it][0]] = 0;
        FOR(i, 1, n)
        {
            int cur = P[it][i];
            int prev = P[it][i - 1];
            CL[it][cur] = CL[it][prev];

            if (CL[it - 1][cur] != CL[it - 1][prev])
            {
                CL[it][cur]++;
                continue;
            }

            int cc = cur;
            cur += 1 << (it - 1);
            if (cur >= n) cur -= n;
            prev += 1 << (it - 1);
            if (prev >= n) prev -= n;

            if (CL[it - 1][cur] != CL[it - 1][prev])
            {
                CL[it][cc]++;
            }
        }
    }

    if (lastLev == -1) lastLev = LEN - 1;
}