UOJ Logo Universal Online Judge

UOJ

#3473. 字符串

统计

Description

给定n个字符串,询问每个字符串有多少子串(不包括空串)是所有n个字符串中至少k个字符串的子串?

Input

第一行两个整数nk
接下来n行每行一个字符串

Output

一行n个整数,第i个整数表示第i个字符串的答案

Sample Input

3 1
abc
a
ab

Sample Output

6 1 3

Hint



对于 100% 的数据,1<=n,k<=10^5,所有字符串总长不超过10^5,字符串只包含小写字母。

Source

Adera 1 杯冬令营模拟赛