#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct {
	const char *podret;
	int pocet;
} ZAZNAM;

int main()
{
	ZAZNAM *tabulka;
	char *retezec=NULL;
	int velikost,n;
	int c,i,k,j,pom,hash;

	velikost=n=0;
	while ((c=getchar())!='\n') {                       /* Ukázka, jak načítat vstup, když předem neznáme jeho délku*/
		if (n>=velikost) {
			velikost=(velikost)?(2*velikost):128;
			retezec=(char*)realloc((void*)retezec,velikost);
		}
		retezec[n++]=c;
	}
	retezec[n]=0;

	for (velikost=2*n+1;;velikost+=2) {                 /* Najdeme nejbližší prvočíslo vyšší než 2N+1 */
		for (i=3;i*i<=velikost && (velikost%i);i+=2);
			if (velikost%i)
				break;
	}

	tabulka=(ZAZNAM*)calloc(velikost,sizeof(ZAZNAM));

	scanf("%d",&k);

	pom=1;                                              /* Spočítáme hash pro prvních k znaků, za P zvolíme třeba 113 */
	for (hash=i=0;i<k;i++) {
		hash=(113*hash+retezec[i])%velikost;
		pom=(113*pom)%velikost;
	}

	tabulka[hash].pocet=1;
	tabulka[hash].podret=retezec;

	for (i=1;i<=n-k;i++) {
		hash=113*hash+retezec[i+k-1];               /* Přepočítáme funkci pro další k-tici */
		hash-=(pom*retezec[i-1])%velikost;
		hash=(hash+velikost)%velikost;

		for (j=hash;tabulka[j].pocet && memcmp(tabulka[j].podret,retezec+i,k);j=(j+1)%velikost);

		tabulka[j].podret=retezec+i;                /* A vložíme do hashovací tabulky */
		tabulka[j].pocet++;
	}

	for (i=0;i<velikost;i++) {                          /* A nakonec vypíšeme výstup */
		if (tabulka[i].pocet) {
			for (j=0;j<k;j++)
				putchar(tabulka[i].podret[j]);
			printf(" %dx\n",tabulka[i].pocet);
		}
	}

	free((void*)retezec);
	free((void*)tabulka);

	return 0;
}