The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 129 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

implementation

string suffix structures

two pointers

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Little Elephant and Strings

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Little Elephant loves strings very much.

He has an array *a* from *n* strings, consisting of lowercase English letters. Let's number the elements of the array from 1 to *n*, then let's denote the element number *i* as *a*_{i}. For each string *a*_{i} (1 ≤ *i* ≤ *n*) the Little Elephant wants to find the number of pairs of integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ |*a*_{i}|) such that substring *a*_{i}[*l*... *r*] is a substring to at least *k* strings from array *a* (including the *i*-th string).

Help the Little Elephant solve this problem.

If you are not familiar with the basic notation in string problems, you can find the corresponding definitions in the notes.

Input

The first line contains two space-separated integers — *n* and *k* (1 ≤ *n*, *k* ≤ 10^{5}). Next *n* lines contain array *a*. The *i*-th line contains a non-empty string *a*_{i}, consisting of lowercase English letter. The total length of all strings *a*_{i} does not exceed 10^{5}.

Output

On a single line print *n* space-separated integers — the *i*-th number is the answer for string *a*_{i}.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 1

abc

a

ab

Output

6 1 3

Input

7 4

rubik

furik

abab

baba

aaabbbababa

abababababa

zero

Output

1 0 9 9 21 30 0

Note

Let's assume that you are given string *a* = *a*_{1}*a*_{2}... *a*_{|a|}, then let's denote the string's length as |*a*| and the string's *i*-th character as *a*_{i}.

A substring *a*[*l*... *r*] (1 ≤ *l* ≤ *r* ≤ |*a*|) of string *a* is string *a*_{l}*a*_{l + 1}... *a*_{r}.

String *a* is a substring of string *b*, if there exists such pair of integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ |*b*|), that *b*[*l*... *r*] = *a*.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 17:58:25 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|