Frequent

An astrobiologist studies life on the planet Alphabet. Life there is DNA-based, and there are 26 nucleotides. So the DNA of a life form from Alphabet is a string of lowercase Latin letters. The astrobiologist has sequenced the DNA of $K$ life forms. The DNA strings are not necessarily distinct, and their total length is $N$ nucleotides. She wants to find the strands (substrings) of DNA that occur frequently among these life forms. Let $L(i)$ be the length of the longest strand of consecutive nucleotides that is common to at least $i$ life forms, for $2 \le i \le K$. $L(i)$ can be 0.

Help the astrobiologist compute the array $L$.

The first line contains an integer $K$, the number of life forms. Each of the next $K$ lines contains a non-empty string of lowercase letters.

Print $K - 1$ lines with the values $L(2), L(3), \ldots, L(K)$, one value per line.

$2 \le N \le 200{,}000$

$2 \le K \le N$

"atter" appears in two of the strings.

"mat" appears in three of the strings.

"ma" (or "at" or "te") appears in four of the strings.

"ma" appears in five of the strings.

"a" appears in all the strings.