E. Маленький Слоник и строки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Слоник очень любит строки.

У него есть массив a из n строк, состоящих из строчных латинских букв. Пусть элементы массива пронумерованы от 1 до n, тогда элемент номер i обозначим ai. Для каждой строки ai (1 ≤ i ≤ n) Маленький Слоник хочет найти количество пар целых чисел l и r (1 ≤ l ≤ r ≤ |ai|) таких, что подстрока ai[l... r] является подстрокой как минимум k строк из массива a (включая i-ю строку).

Помогите Маленькому Слонику решить эту задачу.

Если вы не знакомы с основными обозначениями в строковых задачах, в примечании приведены соответствующие определения.

Входные данные

В первой строке задано два целых числа через пробел — n и k (1 ≤ n, k ≤ 105). В следующих n строках задан массив a. В i-ой строке записана непустая строка ai, состоящая из строчных латинских букв. Суммарная длина всех строк ai не превосходит 105.

Выходные данные

В единственной строке выведите n целых чисел разделенных единичными пробелами — i-е число является ответом для строки ai.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3 1
abc
a
ab
Выходные данные
6 1 3
Входные данные
7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero
Выходные данные
1 0 9 9 21 30 0
Примечание

Пусть задана строка a = a1a2... a|a|, тогда обозначим через |a| длину строки, а через ai — i-й символ строки.

Подстрокой a[l... r] (1 ≤ l ≤ r ≤ |a|) строки a называется строка alal + 1... ar.

Строка a является подстрокой строки b, если существует такая пара целых чисел l и r (1 ≤ l ≤ r ≤ |b|), что b[l... r] = a.