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.

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.

✓	#	Name		✎	Rating↕	Solved↕
	1537E2	Erase and Extend (Hard Version) binary search data structures greedy hashing string suffix structures strings two pointers			2200	6.4k
	204E	Little Elephant and Strings data structures implementation string suffix structures two pointers			2800	1.7k

Problemset