CF204E Little Elephant and Strings

小象非常喜欢字符串。 他有一个由 $n$ 个字符串组成的数组 $a$，所有字符串仅包含小写英文字母。我们将数组的元素编号为 $1$ 到 $n$，第 $i$ 个元素记作 $a_{i}$。对于每个字符串 $a_{i}$（$1 \leq i \leq n$），小象想要找到有多少对整数 $l$ 和 $r$（$1 \leq l \leq r \leq |a_{i}|$），使得子串 $a_{i}[l\ldots r]$ 至少是数组 $a$ 中 $k$ 个字符串（包括第 $i$ 个字符串本身）的一个子串。 请你帮助小象解决这个问题。 如果你不熟悉字符串问题中的基本符号，可以在提示部分找到相应定义。

第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n, k \leq 10^{5}$）。接下来的 $n$ 行，每行包含一个字符串 $a_{i}$，所有 $a_{i}$ 都非空且仅含小写英文字母。所有字符串的总长度不超过 $10^{5}$。

输出一行 $n$ 个用空格分隔的整数，第 $i$ 个数表示字符串 $a_{i}$ 的答案。 请不要在 C++ 代码中使用 %lld 进行 64 位整数的输入输出。推荐使用 cin、cout 流或 %I64d 进行读写。

假设给定字符串 $a=a_{1}a_{2}\ldots a_{|a|}$，则记字符串长度为 $|a|$，第 $i$ 个字符记作 $a_{i}$。 子串 $a[l\ldots r]$（$1 \leq l \leq r \leq |a|$）指的是字符串 $a_{l}a_{l+1}\ldots a_{r}$。 如果存在一对整数 $l$ 和 $r$（$1 \leq l \leq r \leq |b|$），满足 $b[l\ldots r]=a$，那么称字符串 $a$ 是字符串 $b$ 的子串。 由 ChatGPT 5 翻译