← 返回题目列表

Codeforces · 204/E

E. 小象和弦

中文机器翻译题面 查看原题

小象非常喜欢绳子。

他有一个由n个字符串组成的数组a,由小写英文字母组成。让我们将数组的元素从 1 到 n 编号,然后将元素编号 i 表示为 ai。对于每个字符串 ai (1 ≤ i ≤ n),小象想要找到整数对 l 和 r (1 ≤ l ≤ r ≤ |ai|) 的数量,使得子串 ai[l...r] 是数组 a 中至少 k 个字符串(包括第 i 个字符串)的子串。

帮助小象解决这个问题。

如果你不熟悉字符串问题中的基本表示法,可以在注释中找到相应的定义。

输入

第一行包含两个空格分隔的整数 — n 和 k (1 ≤ n, k ≤ 105)。接下来的 n 行包含数组 a。第i行包含一个非空字符串ai,由小写英文字母组成。所有字符串ai的总长度不超过105。

输出

在一行上打印 n 个空格分隔的整数 — 第 i 个数字是字符串 ai 的答案。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3 1
abc
a
ab

输出 #1

6 1 3

输入 #2

7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero

输出 #2

1 0 9 9 21 30 0

注意

假设给定字符串 a = a1a2... a|a|,然后将字符串的长度表示为 |a|字符串的第 i 个字符为 ai。

字符串 a 的子串 a[l... r] (1 ≤ l ≤ r ≤ |a|) 是字符串 alal + 1... ar。

字符串 a 是字符串 b 的子字符串,如果存在整数对 l 和 r (1 ≤ l ≤ r ≤ |b|),则 b[l...r] = a。