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

FILE *input;
FILE *output;

char myBuffer [256];
int buffSize;

typedef struct knot{
    unsigned long long mask;
    int pos;
    struct knot *child[36];
}knot;

knot dictionary [5002];

int Hash(const char liter){
    if ((liter >= 48)&&(liter<=57) ) return (int)(liter - 48);
    return (int)(liter - 87);
}

char BackHash(const int index){
    if ((index >= 0)&&(index<=9) ) return (char)(index + 48);
    return (char)(index + 87);
}

void AddPref(const char liter,const int maxSize){
    static int prefPos = 0;
    static knot *nowKnot = &dictionary[0];

    int index = Hash(liter);
    if ((nowKnot->mask) & (1ULL<<index)){
        nowKnot = (nowKnot->child[index]);
        return;
    }
    if (prefPos>=maxSize){
        prefPos = 0;
        nowKnot = &dictionary[0];
        nowKnot->mask = 0;
    }
    nowKnot->mask |= (1ULL<<index);
    nowKnot->child[index] = &dictionary[prefPos+1];
    nowKnot->child[index]->mask = 0;
    nowKnot->child[index]->pos = prefPos++;
    nowKnot = &dictionary[0];
}

void PrintPref(const knot *nowKnot){
    static char buff [5001];
    static int buffPos = 0;
    for (int i = 0; i < 36;i++){
        if ((nowKnot->mask)&(1ULL<<i)){
            buff[buffPos++] = BackHash(i);
            fprintf(output,"%s %i\n",buff,nowKnot->child[i]->pos);
            PrintPref(nowKnot->child[i]);
            buff[buffPos--] = 0;
        }
    }
}


int main() {

    input = fopen("input.txt", "r");
    output = fopen("output.txt", "w");
    int maxSize;
    fscanf(input,"%i",&maxSize);
    char liter;
    while (!feof(input)){
        buffSize = fread(myBuffer,1,256,input);
        for (int i = 0; i<buffSize;++i) {
            liter = tolower(myBuffer[i]);
            if (((liter >= 97) && (liter <= 122))||((liter >= 48) && (liter <= 57))) {
                AddPref(liter, maxSize);
            }
        }
    }

    PrintPref(&dictionary[0]);

    fclose(input);
    fclose(output);
    return 0;
}