`Ivy` 是一个爱美的妹子，所以她喜欢的东西一定是优美的。

在 `Ivy` 眼里，若干小写字母按照某种特定的顺序排列之后形成的序列是较为优美的，她将其定义为「字符串」。`Ivy` 有 n 个字符串，每天，她会选择一个喜欢的作为自己的配饰。

突然有一天，`Ivy` 发现，某一个字符串可能是另外一个字符串的子串。她认为，如果字符串 $a$ 是字符串 $b$ 的子串，那么 $a$ 就是极其优美的！`Ivy` 被这种美深深震撼。

一年一度的 SDOI 到来了，`Ivy` 当然要盛装出席，所以，她会选择一个最优美的字符串作为自己的配饰。`Ivy` 首先定义了一个优美度参数 $k$，然后某一个字符串 $a$ 的优美度被定义为：字符串 $a$ 有多少个子串（不包括空串）是所有 $n$ 个字符串中至少 $k$ 个字符串的子串（注意包括其本身）。

其中「字符串 $a$ 是字符串 $b$ 的子串」定义为：$a$ 对应了 $b$ 的一段连续的区间，即 $a[1...len(a)]=b[l...r],(1\leq l\leq r\leq len(b))$ 。显然，这个命题成立的充要条件为 $len(a)\leq len(b)$。

现在 `Ivy` 想要考考同样要出席 SDOI 的你，她拥有的每一个字符串的优美度是多少。

时间紧迫，你的任务刻不容缓。

 

---

Sol

bzoj原题。。

考虑