Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está enfrascado en el proyecto final de la asignatura Sistemas de Información. Una parte del proyecto consiste en agrupar documentos semejantes para mejorar los resultados de la búsqueda. Uno de sus compañeros ya resolvió esta parte pero ciertamente Fito no confía mucho en su talento y quiere hacer un módulo que evalúe la calidad de los grupos formados. Fito considera que un grupo es bueno si los documentos que aparecen en él tratan sobre los mismos temas. Una medida de evaluación que propone consiste en determinar para un documento la cantidad de subcadenas que contiene y que aparecen en al menos $K$ de los documentos del grupo. Cada documento es en esencia una cadena compuesta por letras minúsculas. Nuestro desafío en este caso consiste en construir un algoritmo que dadas $N$ cadenas, que representan los documentos a procesar, determine para cada una la medida de evaluación que Fito propone.

La primera línea de la entrada son dos enteros $N$ y $K$ $(1 \leq K, N \leq 10^{5})$ separados por un espacio, representando respectivamente la cantidad de documentos en el conjunto y en cuántos debe aparecer una subcadena. La suma de las longitudes de todos los documentos será menor que $10^{5}$.

La salida debe ser una línea con $N$ enteros separados por un espacio, donde el entero $i$ dice cuántas subcadenas del documento i-ésimo aparecen en al menos $K$ documentos del conjunto.