#include <stdio.h>
#include <malloc.h>
#include <mem.h>
#include <ctype.h>

#define MAX_STR_LEN 1024
#define MAX_HEAP_SIZE 5000
#define MAX_NUM_LNGTH 6
#define ASCII_SIZE 128
#define ALPHABET 36
#define ALPHABET_OFFSET 48

typedef struct t_node {
    struct t_node *child[ALPHABET];
    unsigned long long child_mask;
    int code;
} t_node;

char STR[MAX_STR_LEN];
size_t STR_LENGTH;
t_node HEAP[MAX_HEAP_SIZE + 1], *last = HEAP;
int IND[ASCII_SIZE];


t_node *new();
void *delete_all() { last = HEAP; }
void out(FILE *f, t_node *root, int prev_code);

int main()
{
    int n;
    unsigned long long _ONE_ = 1;
    FILE *f = fopen("input.txt", "r");
    t_node *root, *curr;

    fgets(STR, MAX_NUM_LNGTH, f);
    n = atoi(STR);

    int c;
    for (c = '0'; c <= '9'; ++c)
        IND[c] = c - ALPHABET_OFFSET;
    for (int j = 'a'; j <= 'z'; ++j, ++c)
        IND[j] = c - ALPHABET_OFFSET;

    int k = 0;
    root = new();
    curr = root;
    while (!feof(f)) {
        memset(STR, 0, MAX_STR_LEN);
        fread(STR, sizeof(char), MAX_STR_LEN, f);
        STR_LENGTH = strlen(STR);
        if (STR[STR_LENGTH - 1] == '\n')
            STR[--STR_LENGTH] = '\0';

        for (int i = 0; i < STR_LENGTH; ++i) {
            if (((curr->child_mask >> IND[tolower(STR[i])]) & 1) != 0) {
                curr = curr->child[IND[tolower(STR[i])]];
                continue;
            }

            if (k < n) {
                curr->child[IND[tolower(STR[i])]] = new();
                curr->child_mask |= (_ONE_ << IND[tolower(STR[i])]);
                curr = curr->child[IND[tolower(STR[i])]];
                curr->code = k;
                ++k;
                curr = root;
                continue;
            }

            delete_all();
            root = new();
            root->child[IND[tolower(STR[i])]] = new();
            root->child_mask |= (_ONE_ << IND[tolower(STR[i])]);
            curr = root;
            curr->code = 0;
            k = 1;
        }
    }

    fclose(f);
    f = fopen("output.txt", "w");

    for (int i = 0; i < ALPHABET; ++i) {
        if (((root->child_mask >> i) & 1) != 0) {
            STR[0] = (char) ((i <= IND['9']) ? (i + ALPHABET_OFFSET) : (i + ALPHABET_OFFSET + ('a' - '9' - 1)));
            STR[1] = '\0';
            STR_LENGTH = 1;
            out(f, root->child[i], root->child[i]->code);
        }
    }

    fclose(f);

    return 0;
}

t_node *new()
{
    last->child_mask = (unsigned long long)0;
    return last++;
}

void out(FILE *f, t_node *root, int prev_code)
{
    fprintf(f, "%s %d\n", STR, prev_code);
    if (root->child_mask != 0) {
        char curr[2];
        for (int i = 0; i < ALPHABET; ++i) {
            if (((root->child_mask >> i) & 1) != 0) {
                curr[0] = (char)((i <= IND['9']) ? (i + ALPHABET_OFFSET) : (i + ALPHABET_OFFSET + ('a' - '9' - 1)));
                curr[1] = '\0';
                strcat(STR, curr);
                ++STR_LENGTH;
                out(f, root->child[i], root->child[i]->code);
                STR[--STR_LENGTH] = '\0';
            }
        }
    }
}