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>
namespace MyMinMax {
template <typename T>
inline T mn(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
inline T mx(T x, T y) {
  return x > y ? x : y;
}
template <typename T>
inline void chmin(T &x, T y) {
  (x > y) && (x = y);
}
template <typename T>
inline void chmax(T &x, T y) {
  (x < y) && (x = y);
}
}  // namespace MyMinMax
using namespace MyMinMax;
namespace IO {
char BB[1 << 18], *SS = BB, *TT = BB;
template <typename T = int>
inline T read() {
  T x = 0;
  int fu = 1;
  char c =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
             ? EOF
             : *SS++);
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
             ? EOF
             : *SS++);
  }
  x *= fu;
  return x;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int fu = 1;
  char c =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
             ? EOF
             : *SS++);
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
             ? EOF
             : *SS++);
  }
  x *= fu;
}
template <typename T>
inline void read(T *bg, T *ed) {
  while (bg != ed) read(*bg++);
}
inline void read(char &ch) {
  ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
            ? EOF
            : *SS++);
  while (ch <= 32)
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
}
inline void read(char *s) {
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (ch <= 32)
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  while (ch > 32)
    *s++ = ch,
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  *s = '\0';
}
inline void sread(char *s) {
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (ch < 32)
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  while (ch >= 32)
    *s++ = ch,
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  *s = '\0';
}
inline void pread(char *&s) {
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (ch <= 32)
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  while (ch > 32)
    *s++ = ch,
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  *s = '\0';
}
inline void spread(char *&s) {
  char ch =
      (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
           ? EOF
           : *SS++);
  while (ch < 32)
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  while (ch >= 32)
    *s++ = ch,
    ch = (SS == TT && (TT = (SS = BB) + fread(BB, 1, 1 << 18, stdin), SS == TT)
              ? EOF
              : *SS++);
  *s = '\0';
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
char out[1 << 18], *Out = out;
inline void putcha(char x) {
  *Out++ = x;
  if (Out - out >= (1 << 18)) fwrite(out, 1, Out - out, stdout), Out = out;
}
template <typename T>
inline void fprint(T x) {
  if (x < 0) putcha(45), x = -x;
  if (x > 9) fprint(x / 10);
  putcha(x % 10 + 48);
}
template <typename T>
inline void print(T x) {
  fprint(x);
  putcha(10);
}
inline void print(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
inline void print(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
template <typename T, typename... Args>
inline void print(T x, Args... args) {
  fprint(x);
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename T, typename... Args>
inline void printl(T x, Args... args) {
  fprint(x);
  putcha(10);
  print(args...);
}
template <typename... Args>
inline void printl(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  print(args...);
}
template <typename... Args>
inline void printl(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  print(args...);
}
template <typename T>
inline void sprint(T x) {
  fprint(x);
  putcha(32);
}
template <typename T, typename... Args>
inline void sprint(T x, Args... args) {
  fprint(x);
  putcha(32);
  sprint(args...);
}
template <typename T>
inline void sprint(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
}
template <typename T>
inline void print(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
  putcha(10);
}
template <typename T>
inline void printl(T *bg, T *ed) {
  while (bg != ed) print(*bg++);
}
class AutoFlush {
 public:
  ~AutoFlush() { fwrite(out, 1, Out - out, stdout); }
} __AutoFlush;
}  // namespace IO
using namespace IO;
int n, k, N;
char BUF[100005 << 1], *p[100005];
int t[100005][26], tot;
inline void ins(char *p) {
  int rt = 0;
  for (char *it = p; *it != '\0'; ++it) {
    if (!t[rt][*it - 97]) t[rt][*it - 97] = ++tot;
    rt = t[rt][*it - 97];
  }
}
int len[100005 << 1], link[100005 << 1];
int nxt[100005 << 1][26];
int sz, lst[100005 << 1];
inline int extend(int c, int pre) {
  int x = sz++;
  len[x] = len[pre] + 1;
  int it = pre;
  while (~it && !nxt[it][c]) {
    nxt[it][c] = x;
    it = link[it];
  }
  if (!~it)
    link[x] = 0;
  else {
    int t = nxt[it][c];
    if (len[it] + 1 == len[t])
      link[x] = t;
    else {
      int y = sz++;
      len[y] = len[it] + 1;
      memcpy(nxt[y], nxt[t], sizeof(nxt[y]));
      link[y] = link[t];
      while (~it && nxt[it][c] == t) {
        nxt[it][c] = y;
        it = link[it];
      }
      link[t] = link[x] = y;
    }
  }
  return x;
}
int buf[100005];
inline void layer() {
  link[0] = -1;
  ++sz;
  int *hd = buf, *ed = buf + 1;
  while (hd != ed) {
    int x = *hd++;
    for (int i = (0); i <= (25); ++i)
      if (t[x][i]) {
        *ed++ = t[x][i];
        lst[t[x][i]] = extend(i, lst[x]);
      }
  }
}
int head[100005 << 1], e[100005 << 1], nt[100005 << 1], cnt;
inline void add(int u, int v) {
  nt[++cnt] = head[u];
  head[u] = cnt;
  e[cnt] = v;
}
int s[100005 << 1], tp[100005 << 1], siz[100005 << 1], son[100005 << 1],
    dep[100005 << 1], dfn[100005 << 1], _tot;
void dfs1(int x) {
  siz[x] = 1;
  for (int i = head[x]; i; i = nt[i]) {
    dep[e[i]] = dep[x] + 1;
    dfs1(e[i]);
    siz[x] += siz[e[i]];
    if (siz[son[x]] < siz[e[i]]) son[x] = e[i];
  }
}
void dfs2(int x, int tt) {
  tp[x] = tt;
  dfn[x] = ++_tot;
  if (son[x]) dfs2(son[x], tt);
  for (int i = head[x]; i; i = nt[i]) {
    if (e[i] == son[x]) continue;
    dfs2(e[i], e[i]);
  }
}
inline int LCA(int x, int y) {
  while (tp[x] ^ tp[y]) {
    if (dep[tp[x]] < dep[tp[y]]) std ::swap(x, y);
    x = link[tp[x]];
  }
  if (dep[x] > dep[y])
    return y;
  else
    return x;
}
void dfs(int x) {
  for (int i = head[x]; i; i = nt[i]) dfs(e[i]), s[x] += s[e[i]];
}
inline void build() {
  for (int i = (1); i <= (sz - 1); ++i) add(link[i], i);
  dep[0] = 1;
  dfs1(0);
  dfs2(0, 0);
}
int tmp[100005], ttp;
int fa[100005 << 1][21], c[100005], a[100005 << 1];
inline void prework() {
  for (int i = (0); i <= (sz - 1); ++i) ++c[len[i]];
  for (int i = (1); i <= (N); ++i) c[i] += c[i - 1];
  for (int i = (0); i <= (sz - 1); ++i) a[--c[len[i]]] = i;
  for (int i = (1); i <= (sz - 1); ++i) {
    int x = a[i];
    fa[x][0] = link[x];
    for (int j = (1); j <= (20); ++j) fa[x][j] = fa[fa[x][j - 1]][j - 1];
  }
}
inline bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
inline void init() {
  layer();
  build();
  for (int i = (1); i <= (n); ++i) {
    int rt = 0;
    ttp = 0;
    for (char *it = p[i]; *it != '\0'; ++it) {
      rt = nxt[rt][*it - 97];
      tmp[++ttp] = rt;
      ++s[rt];
    }
    std ::sort(tmp + 1, tmp + ttp + 1, cmp);
    for (int j = (1); j < (ttp); ++j) --s[LCA(tmp[j], tmp[j + 1])];
  }
  dfs(0);
  prework();
}
inline int work(int x) {
  for (int i = (20); i >= (0); --i)
    if (s[fa[x][i]] < k) x = fa[x][i];
  if (s[x] < k) x = link[x];
  return len[x];
}
inline void solve() {
  init();
  for (int i = (1); i <= (n); ++i) {
    int rt = 0;
    long long ans = 0;
    for (char *it = p[i]; *it != '\0'; ++it) {
      rt = nxt[rt][*it - 97];
      ans += work(rt);
    }
    sprint(ans);
  }
  putcha(10);
}
int main() {
  read(n, k);
  char *it = BUF;
  for (int i = (1); i <= (n); ++i) {
    p[i] = ++it;
    pread(it);
    ins(p[i]);
    chmax(N, (int)strlen(p[i]));
  }
  solve();
}
