CF129 E

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

vector <int> build(vector<int> s) {
    int n = (int)s.size();
    const int A = max(256, n + 1);
    vector <int> cnt(A), p(n), c(n);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < A; i++)
        cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;

    c[p[0]] = 0;
    for (int i = 1; i < n; i++)
        c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);

    vector <int> nxt(n), l(n);
    for (int k = 0; (1 << k) < n; k++) {
        for (int i = 0; i < n; i++)
            l[i] = (p[i] - (1 << k) + n) % n;
        fill(cnt.begin(), cnt.begin() + c[p.back()] + 1, 0);
        for (int i = 0; i < n; i++)
            cnt[c[l[i]]]++;
        for (int i = 1; i <= c[p.back()]; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--)
            p[--cnt[c[l[i]]]] = l[i];

        nxt[p[0]] = 0;
        for (int i = 1; i < n; i++)
            nxt[p[i]] = nxt[p[i - 1]] +
                        (make_pair(c[p[i]], c[(p[i] + (1 << k)) % n]) != make_pair(c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]));
        c.swap(nxt);
    }
    return p;
}

int n, k;

const int N = 2e5 + 128;
const int LOG = 19;
int dp[N][LOG], lg2[N];

int get(int l, int r) {
    int k = lg2[r-l+1];
    return min(dp[l][k], dp[r-(1<<k)+1][k]);
}

void solve() {
    cin >> n >> k;
    vector <int> total, after;
    set <int> bad;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        after.push_back((int)total.size());
        for (int c = 0; c < (int)s.size(); c++)
            total.push_back(int(s[c]) + n + 1);
        bad.insert((int)total.size());
        total.push_back(n-i);
    }

    vector <int> to_compress = total;
    sort(all(to_compress));
    to_compress.resize(unique(all(to_compress)) - to_compress.begin());
    map <int, int> val;
    for (int i = 0; i < (int)to_compress.size(); i++)
        val[to_compress[i]] = i;
    for (int i = 0; i < (int)total.size(); i++)
        total[i] = val[total[i]];

    vector <int> p = build(total);

    int sz = (int)p.size();
    vector <int> pos(sz);
    for (int i = 0; i < sz; i++)
        pos[p[i]] = i;

    vector <int> lcp(sz, 0);
    int len = 0;

    for (int i = 0; i + 1 < sz; i++) {
        len = max(len - 1, 0);

        int c = pos[i];
        int j = p[c - 1];

        while (total[i + len] == total[j + len])
            ++len;

        lcp[c - 1] = len;
    }

    int m = sz - 1;
    for (int i = 0; i < m; i++)
        dp[i][0] = lcp[i];
    for (int b = 1; b < LOG; b++)
        for (int i = 0; i < m; i++)
            if (i + (1 << b) - 1 < m)
                dp[i][b] = min(dp[i][b - 1], dp[i + (1 << (b - 1))][b - 1]);

    vector <int> host(sz);
    for (int i = 0; i < sz; i++)
        if (bad.count(p[i]))
            host[i] = -1;
        else
            host[i] = (int)(upper_bound(all(after), p[i]) - after.begin());

    vector <int> R(sz, 1e9);
    set <int> st;
    map <int, int> cnt;

    auto add = [&](int x) -> void {
        if (cnt[x] == 0)
            st.insert(x);
        cnt[x]++;
    };

    auto del = [&](int x) -> void {
        cnt[x]--;
        if (cnt[x] == 0)
            st.erase(x);
    };

    auto get_size = [&]() -> int {
        return (int)st.size() - st.count(-1);
    };

    int to = -1;
    for (int i = 0; i < sz; i++) {
        while (to + 1 < sz && get_size() < k)
            add(host[++to]);

        if (get_size() >= k)
            R[i] = to;
        del(host[i]);
    }

    vector <ll> res(n + 1);

    for (int i = 0; i < sz; i++) {
        if (host[i] == -1)
            continue;
        auto check = [&](int x) -> bool {
            int l = i;
            if (i && lcp[i - 1] >= x) {
                int lx = 0, rx = i - 1;
                while (lx + 1 < rx) {
                    int mx = (lx + rx) >> 1;
                    if (get(mx, i - 1) >= x)
                        rx = mx;
                    else
                        lx = mx;
                }
                if (get(lx, i - 1) >= x) l = lx;
                else l = rx;
            }

            int r = i;
            if (lcp[i] >= x) {
                int lx = i, rx = sz - 1;
                while (lx + 1 < rx) {
                    int mx = (lx + rx) >> 1;
                    if (get(i, mx) < x)
                        rx = mx;
                    else
                        lx = mx;
                }
                if (get(i, rx) < x) r = rx;
                else r = lx;
            }

            return R[l] <= r;
        };
        int nxt_bad = *bad.lower_bound(p[i])-p[i];
        int l = 0, r = nxt_bad + 1;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (check(m))
                l = m;
            else
                r = m;
        }
        res[host[i]] += l;
    }

    for (int i = 1; i <= n; i++)
        cout << res[i] << ' ';
    cout << '\n';

}

main() {
    boost;

    for (int i = 2; i < N; i++)
        lg2[i] = lg2[i / 2] + 1;

    solve();
    return 0;
}