Migrated from Lutece 3062 k substring

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定 $n$ 个字符串 $S_1,S_2,\ldots,S_n$。对于每个字符串 $S_i$，求它有多少非空子串是所有 $n$ 个字符串中至少 $k$ 个字符串的子串。

两个子串不同，当且仅当他们在原串中的位置不同或长度不同。

Input

第一行两个整数 $n$ 和 $k$。

接下来 $n$ 行，每行一个字符串。

Output

输出一行 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个字符串的答案。

Samples

3 1
abc
a
ab

6 1 3

5 3
cb
c
aabcc
b
bcb

2 1 3 1 3

Constraints

$1\le n,k\le 10^5$ $S_i\ge 1$ $\sum |S_i|\le 10^5$

Resources

2023 UESTC ICPC Training for String