小象非常喜欢绳子。
他有一个由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。