The Little Elephant loves strings very much. 

He has an array a from n strings, consisting of lowercase English letters. Let's number the elements of the array from 1 to n, then let's denote the element number i as ai. For each string ai (1 ≤ i ≤ n) the Little Elephant wants to find the number of pairs of integers l and r (1 ≤ l ≤ r ≤ |ai|) such that substring ai[l... r] is a substring to at least k strings from array a (including the i-th string).

Help the Little Elephant solve this problem.

If you are not familiar with the basic notation in string problems, you can find the corresponding definitions in the notes.

Input

The first line contains two space-separated integers — n and k (1 ≤ n, k ≤ 105). Next n lines contain array a. The i-th line contains a non-empty string ai, consisting of lowercase English letter. The total length of all strings ai does not exceed 105.

Output

On a single line print n space-separated integers — the i-th number is the answer for string ai.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 1
abc
a
ab


Output

6 1 3 


Input

7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero


Output

1 0 9 9 21 30 0 

Note

Let's assume that you are given string a = a1a2... a|a|, then let's denote the string's length as |a| and the string's i-th character as ai.

A substring a[l... r] (1 ≤ l ≤ r ≤ |a|) of string a is string alal + 1... ar.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l... r] = a.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
unsigned char mask[] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
const int maxn = 6e5 + 5;
int sa[maxn];
int rankk[maxn];
unsigned char *s;
int nn;
void getBuckets(unsigned char *s, int *bkt, int nn, int K, int cs, bool end) {
  int i, sum = 0;
  for (i = 0; i <= K; i++) bkt[i] = 0;
  for (i = 0; i < nn; i++)
    bkt[(cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i])]++;
  for (i = 0; i <= K; i++) {
    sum += bkt[i];
    bkt[i] = end ? sum : sum - bkt[i];
  }
}
void induceSAl(unsigned char *t, int *SA, unsigned char *s, int *bkt, int nn,
               int K, int cs, bool end) {
  int i, j;
  getBuckets(s, bkt, nn, K, cs, end);
  for (i = 0; i < nn; i++) {
    j = SA[i] - 1;
    if (j >= 0 && !((t[(j) / 8] & mask[(j) % 8]) ? 1 : 0))
      SA[bkt[(cs == sizeof(int) ? ((int *)s)[j] : ((unsigned char *)s)[j])]++] =
          j;
  }
}
void induceSAs(unsigned char *t, int *SA, unsigned char *s, int *bkt, int nn,
               int K, int cs, bool end) {
  int i, j;
  getBuckets(s, bkt, nn, K, cs, end);
  for (i = nn - 1; i >= 0; i--) {
    j = SA[i] - 1;
    if (j >= 0 && ((t[(j) / 8] & mask[(j) % 8]) ? 1 : 0))
      SA[--bkt[(cs == sizeof(int) ? ((int *)s)[j] : ((unsigned char *)s)[j])]] =
          j;
  }
}
void SA_IS(unsigned char *s, int *SA, int nn, int K, int cs) {
  int i, j;
  unsigned char *t = (unsigned char *)malloc(nn / 8 + 1);
  t[(nn - 2) / 8] = (0) ? (mask[(nn - 2) % 8] | t[(nn - 2) / 8])
                        : ((~mask[(nn - 2) % 8]) & t[(nn - 2) / 8]);
  t[(nn - 1) / 8] = (1) ? (mask[(nn - 1) % 8] | t[(nn - 1) / 8])
                        : ((~mask[(nn - 1) % 8]) & t[(nn - 1) / 8]);
  for (i = nn - 3; i >= 0; i--)
    t[(i) / 8] =
        (((cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i]) <
              (cs == sizeof(int) ? ((int *)s)[i + 1]
                                 : ((unsigned char *)s)[i + 1]) ||
          ((cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i]) ==
               (cs == sizeof(int) ? ((int *)s)[i + 1]
                                  : ((unsigned char *)s)[i + 1]) &&
           ((t[(i + 1) / 8] & mask[(i + 1) % 8]) ? 1 : 0) == 1))
             ? 1
             : 0)
            ? (mask[(i) % 8] | t[(i) / 8])
            : ((~mask[(i) % 8]) & t[(i) / 8]);
  int *bkt = (int *)malloc(sizeof(int) * (K + 1));
  getBuckets(s, bkt, nn, K, cs, true);
  for (i = 0; i < nn; i++) SA[i] = -1;
  for (i = 1; i < nn; i++)
    if ((i > 0 && ((t[(i) / 8] & mask[(i) % 8]) ? 1 : 0) &&
         !((t[(i - 1) / 8] & mask[(i - 1) % 8]) ? 1 : 0)))
      SA[--bkt[(cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i])]] =
          i;
  induceSAl(t, SA, s, bkt, nn, K, cs, false);
  induceSAs(t, SA, s, bkt, nn, K, cs, true);
  free(bkt);
  int nn1 = 0;
  for (i = 0; i < nn; i++)
    if ((SA[i] > 0 && ((t[(SA[i]) / 8] & mask[(SA[i]) % 8]) ? 1 : 0) &&
         !((t[(SA[i] - 1) / 8] & mask[(SA[i] - 1) % 8]) ? 1 : 0)))
      SA[nn1++] = SA[i];
  for (i = nn1; i < nn; i++) SA[i] = -1;
  int nname = 0, prev = -1;
  for (i = 0; i < nn1; i++) {
    int pos = SA[i];
    bool diff = false;
    for (int d = 0; d < nn; d++)
      if (prev == -1 ||
          (cs == sizeof(int) ? ((int *)s)[pos + d]
                             : ((unsigned char *)s)[pos + d]) !=
              (cs == sizeof(int) ? ((int *)s)[prev + d]
                                 : ((unsigned char *)s)[prev + d]) ||
          ((t[(pos + d) / 8] & mask[(pos + d) % 8]) ? 1 : 0) !=
              ((t[(prev + d) / 8] & mask[(prev + d) % 8]) ? 1 : 0)) {
        diff = true;
        break;
      } else if (d > 0 &&
                 ((pos + d > 0 &&
                   ((t[(pos + d) / 8] & mask[(pos + d) % 8]) ? 1 : 0) &&
                   !((t[(pos + d - 1) / 8] & mask[(pos + d - 1) % 8]) ? 1
                                                                      : 0)) ||
                  (prev + d > 0 &&
                   ((t[(prev + d) / 8] & mask[(prev + d) % 8]) ? 1 : 0) &&
                   !((t[(prev + d - 1) / 8] & mask[(prev + d - 1) % 8]) ? 1
                                                                        : 0))))
        break;
    if (diff) {
      nname++;
      prev = pos;
    }
    pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
    SA[nn1 + pos] = nname - 1;
  }
  for (i = nn - 1, j = nn - 1; i >= nn1; i--)
    if (SA[i] >= 0) SA[j--] = SA[i];
  int *SA1 = SA, *s1 = SA + nn - nn1;
  if (nname < nn1)
    SA_IS((unsigned char *)s1, SA1, nn1, nname - 1, sizeof(int));
  else
    for (i = 0; i < nn1; i++) SA1[s1[i]] = i;
  bkt = (int *)malloc(sizeof(int) * (K + 1));
  getBuckets(s, bkt, nn, K, cs, true);
  for (i = 1, j = 0; i < nn; i++)
    if ((i > 0 && ((t[(i) / 8] & mask[(i) % 8]) ? 1 : 0) &&
         !((t[(i - 1) / 8] & mask[(i - 1) % 8]) ? 1 : 0)))
      s1[j++] = i;
  for (i = 0; i < nn1; i++) SA1[i] = s1[SA1[i]];
  for (i = nn1; i < nn; i++) SA[i] = -1;
  for (i = nn1 - 1; i >= 0; i--) {
    j = SA[i];
    SA[i] = -1;
    SA[--bkt[(cs == sizeof(int) ? ((int *)s)[j] : ((unsigned char *)s)[j])]] =
        j;
  }
  induceSAl(t, SA, s, bkt, nn, K, cs, false);
  induceSAs(t, SA, s, bkt, nn, K, cs, true);
  free(bkt);
  free(t);
}
vector<int> kasai(string txt, const vector<int> &suffixArr) {
  int n = suffixArr.size();
  vector<int> lcp(n, 0);
  vector<int> invSuff(n, 0);
  for (int i = 0; i < nn; i++) invSuff[suffixArr[i]] = i;
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (invSuff[i] == n - 1) {
      k = 0;
      continue;
    }
    int j = suffixArr[invSuff[i] + 1];
    while (i + k < n && j + k < n && txt[i + k] == txt[j + k]) k++;
    lcp[invSuff[i]] = k;
    if (k > 0) k--;
  }
  return lcp;
}
vector<int> buildSA(string ss) {
  vector<int> temp;
  nn = ss.size();
  s = (unsigned char *)ss.c_str();
  SA_IS(s, sa, nn + 1, 256, 1);
  for (int i = 1; i <= nn; i++) temp.push_back(sa[i]);
  return temp;
}
const int N = 6e5 + 5;
int m1[N], m2[N];
vector<int> sarr, lcp;
int tr[4 * N], tot;
void build(int nd, int s, int e) {
  if (s == e) {
    tr[nd] = lcp[s];
    return;
  }
  int m = (s + e) >> 1;
  build(nd << 1, s, m);
  build(nd << 1 | 1, m + 1, e);
  tr[nd] = min(tr[nd << 1], tr[nd << 1 | 1]);
}
int lquery(int nd, int s, int e, int l, int r, int val) {
  if (s > r || e < l || l > r) return -1;
  if (tr[nd] >= val) return -1;
  if (s == e) return s;
  int m = (s + e) >> 1;
  int q = lquery(nd << 1 | 1, m + 1, e, l, r, val);
  if (q == -1) q = lquery(nd << 1, s, m, l, r, val);
  return q;
}
int rquery(int nd, int s, int e, int l, int r, int val) {
  if (s > r || e < l || l > r) return -1;
  if (tr[nd] >= val) return -1;
  if (s == e) return s;
  int m = (s + e) >> 1;
  int q = rquery(nd << 1, s, m, l, r, val);
  if (q == -1) q = rquery(nd << 1 | 1, m + 1, e, l, r, val);
  return q;
}
int lquery(int l, int r, int val) { return lquery(1, 0, tot - 1, l, r, val); }
int rquery(int l, int r, int val) { return rquery(1, 0, tot - 1, l, r, val); }
int color[N], temp[N], pp[N], lol[N];
map<int, int> m3;
vector<int> tr1[4 * N];
void build1(int nd, int s, int e) {
  sort(tr1[nd].begin(), tr1[nd].end());
  if (s == e) {
    if (color[s]) tr1[nd].push_back(pp[s]);
    return;
  }
  int m = (s + e) >> 1;
  build1(nd << 1, s, m);
  build1(nd << 1 | 1, m + 1, e);
  tr1[nd].resize(tr1[nd << 1].size() + tr1[nd << 1 | 1].size());
  merge(tr1[nd << 1].begin(), tr1[nd << 1].end(), tr1[nd << 1 | 1].begin(),
        tr1[nd << 1 | 1].end(), tr1[nd].begin());
}
int query(int nd, int s, int e, int l, int r, int val) {
  if (s > r || e < l || l > r) return 0;
  if (l <= s && e <= r) {
    return lower_bound(tr1[nd].begin(), tr1[nd].end(), val) - tr1[nd].begin();
  }
  int m = (s + e) >> 1;
  return query(nd << 1, s, m, l, r, val) +
         query(nd << 1 | 1, m + 1, e, l, r, val);
}
int dist_query(int l, int r) {
  return query(1, 0, tot - 1, 0, r, l) - (l == 0 ? 0 : lol[l - 1]);
}
int n, k;
string st[N], ss = "";
bool check(int idx, int l, int r) {
  int p1 = m1[idx] + l;
  int p2 = m2[p1];
  int len = r - l + 1;
  int l1 = lquery(0, p2 - 1, len) + 1, r1 = rquery(p2, tot - 1, len);
  return dist_query(l1, r1) >= k;
}
signed main() {
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    m1[i] = ss.size();
    cin >> st[i];
    ss += st[i];
    int len = ss.size();
    for (int j = m1[i]; j < len; j++) {
      temp[j] = i;
    }
    ss += to_string(i);
  }
  sarr = buildSA(ss);
  lcp = kasai(ss, sarr);
  tot = ss.size();
  for (int i = 0; i < tot; i++) {
    m2[sarr[i]] = i;
    color[i] = temp[sarr[i]];
    lol[i] = lol[i - 1];
    if (!color[i]) continue;
    lol[i]++;
    if (!m3.count(color[i]))
      pp[i] = -1;
    else
      pp[i] = m3[color[i]];
    m3[color[i]] = i;
  }
  build(1, 0, tot - 1);
  build1(1, 0, tot - 1);
  for (int i = 1; i <= n; i++) {
    long long int ans = 0;
    int len = st[i].size();
    int r = -1;
    for (int j = 0; j <= len - 1; j++) {
      r = max(r, j - 1);
      while (r + 1 < len && check(i, j, r + 1)) {
        r++;
        ans += r - j + 1;
      }
    }
    cout << ans << " ";
  }
  return 0;
}
