Little Elephant and Strings

3000ms

262144K

Description:

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 a_i. For each string a_i (1 ≤ i ≤ n) the Little Elephant wants to find the number of pairs of integers l and r (1 ≤ l ≤ r ≤ |a_i|) such that substring a_i[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 ≤ 10⁵). Next n lines contain array a. The i-th line contains a non-empty string a_i, consisting of lowercase English letter. The total length of all strings a_i does not exceed 10⁵.

Output:

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

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.

Sample Input:

3 1
abc
a
ab

Sample Output:

6 1 3

Sample Input:

7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero

Sample Output:

1 0 9 9 21 30 0

Note:

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

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

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.

Informação

Provedor Codeforces

Código CF204E