SAIS

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>

struct Stroka {
    std::vector<int> str;
    int start;
    int same = -1;
};

class SAIS {
public:
    SAIS::SAIS(std::vector<int> str) : str(str) {}
    std::vector<int> GetSA();
private:
    std::vector<int> str;
    std::vector<int> type;
    std::vector<int> sstar;
    std::set<int> alphabet;
    std::vector<Stroka> sort;
    std::vector<std::vector<int>> star;
    std::vector<std::deque<int>> minus;
    std::vector<std::deque<int>> plus;
    int alph_size;

    void getAlphabetSize();
    std::vector<int> sufMas();
    void setType();
    void radixSort(int l, int r, int j);
    void sortMinus();
    void sortPlus();
};

int maxChar = -1;

void SAIS::radixSort(int l, int r, int j) {
    if (r - l < 1) {
        return;
    }
    if (r - l == 1) {
        maxChar++;
        sort[l].same = maxChar;
        return;
    }
    std::vector<std::vector<Stroka>> mas(alph_size + 1);
    std::vector<Stroka> shor;
    for (int i = l; i < r; i++) {
        if (sort[i].str.size() <= j) {
            shor.push_back(sort[i]);
        }
        else {
            mas[sort[i].str[j]].push_back(sort[i]);
        }
    }
    int q = l;
    for (int i = 0; i < shor.size(); i++) {
        if (i == 0)
            maxChar++;
        sort[q] = shor[i];
        sort[q].same = maxChar;
        q++;
    }
    for (int i = 0; i < alph_size + 1; i++) {
        for (int k = 0; k < mas[i].size(); k++) {
            sort[q] = mas[i][k];
            q++;
        }
        radixSort(q - mas[i].size(), q, j + 1);
    }
}

void SAIS::getAlphabetSize() {
    for (int i = 0; i < str.size(); i++) {
        alphabet.insert(str[i]);
    }
}

std::vector<int> SAIS::sufMas() {
    std::vector<std::vector<int>> buckets(alph_size);
    for (int i = 0; i < str.size(); i++) {
        buckets[str[i]].push_back(i);
    }
    std::vector<int> sufmas;
    for (int i = 0; i < alph_size; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            sufmas.push_back(buckets[i][j]);
        }
    }
    return sufmas;
}

void SAIS::setType() {
    type[str.size() - 1] = 2;
    sstar.push_back(str.size() - 1);
    for (int i = str.size() - 2; i >= 0; i--) {
        if (str[i] < str[i + 1])
            type[i] = 1;
        else if (str[i] > str[i + 1])
            type[i] = 0;
        else if (type[i + 1] == 0)
            type[i] = 0;
        else
            type[i] = 1;

        if (type[i + 1] == 1 && type[i] == 0) {
            type[i + 1] = 2;
            sstar.push_back(i + 1);
        }
    }
    std::reverse(sstar.begin(), sstar.end());
}

void SAIS::sortMinus() {
    minus[str[str.size() - 2]].push_back(str.size() - 2);
    std::deque<int> c;
    for (int i = 1; i < alph_size; i++) {
        c.clear();
        while(!minus[i].empty()) {
            int letter = minus[i][0];
            minus[i].pop_front();
            c.push_back(letter);
            if (letter > 0 && str[letter - 1] >= i) {
                minus[str[letter - 1]].push_back(letter - 1);
            }
        }
        minus[i] = c;
        for (int j = 0; j < star[i].size(); j++) {
            minus[str[star[i][j] - 1]].push_back(star[i][j] - 1);
        }
    }

}

void SAIS::sortPlus () {
    std::deque<int> c;
    for (int i = alph_size - 1; i >= 1; i--) {
        c.clear();
        while (!plus[i].empty()) {
            int letter = plus[i].back();
            plus[i].pop_back();
            c.push_front(letter);
            if (letter > 0 && str[letter - 1] <= i) {
                plus[str[letter - 1]].push_front(letter - 1);
            }
        }
        plus[i] = c;
        for (int j = minus[i].size() - 1; j >= 0; j--) {
            if (minus[i][j] - 1 >= 0 && str[minus[i][j] - 1] < i) {
                plus[str[minus[i][j] - 1]].push_front(minus[i][j] - 1);
            }
        }
    }
}

std::vector<int> SAIS::GetSA() {
    getAlphabetSize();
    auto it = alphabet.end();
    it--;
    alph_size = *(it) + 1;
    if (alphabet.size() == str.size()) {
        return sufMas();
    }
    type.resize(str.size());
    setType();
    sort.resize(sstar.size());
    for (int i = 0; i < sstar.size() - 1; i++) {
        sort[i].start = sstar[i];
        for (int j = sstar[i]; j <= sstar[i + 1]; j++) {
            sort[i].str.push_back(str[j]);
        }
        sort[i].str.push_back(alph_size);
    }
    sort.back().start = sstar.back();
    sort.back().str = { 0 };
    maxChar = -1;
    radixSort(0, sort.size(), 0);
    std::vector<int> help(str.size(), -1);
    std::vector<int> help1(str.size(), -1);
    for (int i = 0; i < sort.size(); i++) {
        help[sort[i].start] = sort[i].same;
        help1[sort[i].start] = i;
    }
    std::vector<int> new_str;
    std::vector<int> new_str1;
    for (int i = 0; i < str.size(); i++) {
        if (help[i] > -1) {
            new_str.push_back(help[i]);
            new_str1.push_back(help1[i]);
        }
    }
    SAIS a(new_str);
    std::vector<int> suffmas1 = a.GetSA();
    star.resize(alph_size);
    for (int i = 0; i < suffmas1.size(); i++) {
        star[sort[new_str1[suffmas1[i]]].str[0]].push_back(sort[new_str1[suffmas1[i]]].start);
    }
    minus.resize(alph_size);
    plus.resize(alph_size);
    sortMinus();
    sortPlus();
    std::vector<int> sufmas = { static_cast<int>(str.size() - 1) };
    for (int i = 1; i < alph_size; i++) {
        sufmas.insert(sufmas.end(), minus[i].begin(), minus[i].end());
        sufmas.insert(sufmas.end(), plus[i].begin(), plus[i].end());
    }
    return sufmas;
}

void kasai(std::vector<int>& str, std::vector<int>& sufmas, std::vector<int>& lcp) {
    int n = str.size();
    std::vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        pos[sufmas[i]] = i;
    }
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (k > 0) {
            k--;
        }
        if (pos[i] == n - 1) {
            lcp[n - 1] = -1;
            k = 0;
        }
        else {
            int j = sufmas[pos[i] + 1];
            while (std::max(i + k, j + k) < n && str[i + k] == str[j + k])
                k++;
            lcp[pos[i]] = k;
        }
    }
}

int main() {
    int k = 0;
    std::cin >> k;
    std::vector<int> str;
    std::string str1;
    std::cin >> str1;
    int n = str1.length();
    while (str1.length() < n + k) {
        str1 += str1;
    }
    for (int j = 0; j < n; j++) {
        std::string str2 = str1.substr(j, k);
        str.clear();
        for (int i = 0; i < str2.size(); i++)
        {
            str.push_back(str2[i] - 'a' + 1);
        }
        str.push_back(0);
        SAIS a(str);
        std::vector<int> sufmas = a.GetSA();
        std::vector<int> lcp(str.size());
        kasai(str, sufmas, lcp);
        int ans = (str.size())*(str.size() - 1) / 2;
        ans -= std::accumulate(lcp.begin(), lcp.end(), 0) + 1;
        std::cout << ans << ' ';
    }
    return 0;
}