CF204E.Little Elephant and Strings

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.

小象非常喜欢字符串。

他有一个由 $n$ 个字符串组成的数组 $a$，每个字符串仅包含小写英文字母。我们将数组元素编号为 $1$ 到 $n$，并用 $a_i$ 表示第 $i$ 个元素。对于每个字符串 $a_i$（其中 $1 \le i \le n$），小象希望找出满足如下条件的整数对 $(l, r)$ 的数量：
$1 \le l \le r \le |a_i|$，且子串 $a_i[l\ldots r]$ 至少是数组 $a$ 中 $k$ 个字符串（包括第 $i$ 个字符串本身）的子串。

请帮助小象解决这个问题。

如果你不熟悉字符串问题中的基本记号，可参见题末的注释部分。

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 a__i, consisting of lowercase English letter. The total length of all strings a__i does not exceed 105.

第一行包含两个以空格分隔的整数 — $n$ 和 $k$（$1 ≤ n, k ≤ 10^5$）。接下来的 $n$ 行包含数组 $a$。第 $i$ 行包含一个非空字符串 $a_i$，由小写英文字母组成。所有字符串 $a_i$ 的总长度不超过 $10^5$。

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.

在一行中输出 n 个空格分隔的整数——第 i 个数是字符串 a__i 对应的答案。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流或 %I64d 说明符。

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

假设给定字符串 $a = a_1a_2\ldots a_{|a|}$，我们记该字符串的长度为 $|a|$，其第 $i$ 个字符为 $a_i$。

字符串 $a$ 的子串 $a[l\ldots r]$（其中 $1 \le l \le r \le |a|$）定义为字符串 $a_la_{l+1}\ldots a_r$。

若存在一对整数 $l$ 和 $r$（满足 $1 \le l \le r \le |b|$），使得 $b[l\ldots r] = a$，则称字符串 $a$ 是字符串 $b$ 的子串。