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.

输入描述:

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.

输出描述:

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.

备注:

Let's assume that you are given string a = a1a2... aa, 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.