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

typedef struct dicionario
{
    char chave[21];

    int* linhas;

    int tam_linhas;

}Dicionario;

void inicializa(Dicionario* tabela, int tam)
{
    int i;

    for(i=0; i < tam; i++)
        tabela[i].tam_linhas = 0;
}

int code(char str[])//gera um codigo p a chave
{
    int tam_str = strlen(str),aux=0, i, j;

    for(i=0,j=tam_str-1; i < tam_str; i++,j--)
        aux = aux + (str[i]-'a')*(pow(26,j));

    return aux;
}

int hash(int chave, int tam, int i)
{
    return (chave%tam + i);
}

int naoTemRepeticaoDaLinha(int linha, int v[], int tam)
{
    int i;//índice de reaplicação do Hash

    char existe = 'N';

    for(i = 0; i < tam; i++)
        if(v[i] == linha)
            existe = 'S';

    return (existe == 'N');
}

void insereTabela(char* aux, Dicionario* tabela, int tam, int num_linha, int* num_chaves)
{
    int pos, i=0;

    char op_efetuada = 'N';

    pos = hash(code(aux), tam, i);

    //printf("%d\n", pos);

    while(op_efetuada == 'N')
    {

        if(tabela[pos].tam_linhas == 0)//se nao houve conflito
        {
            strcpy(tabela[pos].chave, aux);//atualiza a chave

            tabela[pos].tam_linhas++;//atualiza o tamanho

            tabela[pos].linhas = (int*) malloc(sizeof(int));//cria o vetor de linhas

            if(tabela[pos].linhas == NULL)
            {
                printf("\nmemoria insuficiente");

                exit(1);
            }

            tabela[pos].linhas[tabela[pos].tam_linhas - 1] = num_linha;//add a linha atual

            op_efetuada = 'S';

            *num_chaves = *num_chaves + 1;

        }
        else//houve conflito
        {

            if(strcmp(aux, tabela[pos].chave) == 0)//se a chave coincidir
            {
                if(naoTemRepeticaoDaLinha(num_linha, tabela[pos].linhas, tabela[pos].tam_linhas))//se não houver repeticao de linha
                {
                    tabela[pos].tam_linhas++;

                    tabela[pos].linhas = (int*) realloc(tabela[pos].linhas, (tabela[pos].tam_linhas)*sizeof(int) );

                    if(tabela[pos].linhas == NULL)
                    {
                        printf("\nmemoria insuficiente");

                        exit(1);
                    }

                    tabela[pos].linhas[tabela[pos].tam_linhas - 1] = num_linha;

                    op_efetuada = 'S';
                }
            }
            else//procura outra posicao
            {
                i++;

                pos = hash(code(aux), tam, i);
            }

        }
    }
}

void reallocaTabela(Dicionario* tabela, Dicionario* tabela2, int tam, int tam_temp)
{
    int i,
        j,
        k,
        pos;

    char op_efetuada;

    for(i=0; i < tam_temp; i++)
    {
        op_efetuada == 'N';

        if(tabela[i].tam_linhas != 0)
        {
            j=0;

            pos = hash(code(tabela[i].chave), tam, j);

            while(op_efetuada == 'N')
            {
                if(tabela2[pos].tam_linhas == 0)//se nao houve conflito
                {
                    strcpy(tabela2[pos].chave, tabela[i].chave);//atualiza a chave

                    tabela2[pos].tam_linhas = tabela[i].tam_linhas;//atualiza o tamanho

                    tabela2[pos].linhas = (int*) malloc(tabela2[pos].tam_linhas*sizeof(int));//cria o vetor de linhas

                    if(tabela2[pos].linhas == NULL)
                    {
                        printf("\nmemoria insuficiente");

                        exit(1);
                    }

                    for(k=0; k < tabela2[pos].tam_linhas; k++)
                        tabela2[pos].linhas[k] = tabela[i].linhas[k];

                    op_efetuada = 'S';

                }
                else//procura outra posicao
                {
                    j++;

                    pos = hash(code(tabela[i].chave), tam, j);
                }
            }
        }
    }
}


///MAIN


int main()
{
    int tam=11,
        num_chaves=0,
        i,//coeficiente anti-colisão
        num_linha = 1,
        tam_temp,
        k,
        pos;

    float load_factor=0;//razão entre o número de chaves distintas na tabela e a capacidade máxima da tabela

    char str[101], op_efetuada;

    Dicionario* tabela = (Dicionario*) malloc(tam*sizeof(Dicionario));

    Dicionario* tabela2;

    if(tabela == NULL)
    {
        printf("\nmemoria insuficiente");

        exit(1);
    }

    inicializa(tabela, tam);//inicializa tabela com tam_linhas = 0;

    freopen("L3Q1.in","r",stdin);
    freopen("L3Q1.out","w",stdout);

    gets(str);//lê $TEXTO

    //enquanto tiver linhas do texto para ler
    while (scanf(" %100[^\n]", str) && strcmp(str, "$CONSULTAS") != 0)
    {
        load_factor = (float) num_chaves/tam;

        if(load_factor > 0.5 && num_chaves < 6000)//se load_factor for maior que 1/2
        {
            tam_temp = tam;

            tam = tam*2 + 1;//duplique o tam

            tabela2 = (Dicionario*) malloc(tam*sizeof(Dicionario));

            if(tabela2 == NULL)
            {
                printf("\nmemoria insuficiente");

                exit(1);
            }

            inicializa(tabela2, tam);

            reallocaTabela(tabela, tabela2, tam, tam_temp);

            free(tabela);

            tabela = tabela2;
        }

        char* aux = strtok(str, " ");//strtok vai separar a string nas palavras


        while (aux != NULL)
        {
            //printf("%s\n", aux);
            insereTabela(aux, tabela, tam, num_linha, &num_chaves);

            aux = strtok(NULL, " ");
        }

        num_linha++;
    }

    //como no loop acima ja lemos o $CONSULTAS, so precisamos ler as consultas
    while (scanf(" %20[^\n]", str) == 1)//enquanto tiver consulta para ler
    {
        i=0;

        k=num_chaves;

        op_efetuada == 'N';

        pos = hash(code(str), tam, i);

        while(op_efetuada == 'N')
        {
            if(strcmp(tabela[pos].chave,str) == 0)
            {
                printf("%s: ",str);

                //tam_temp faz papel de contador
                for(tam_temp = 0; tam_temp < tabela[pos].tam_linhas; tam_temp++)
                    printf("%d ", tabela[pos].linhas[tam_temp]);

                printf("\n");

                op_efetuada == 'S';
            }
            else
            {
                if(k>0)
                {
                    i++;

                    pos = hash(code(str), tam, i);

                    k--;
                }
                else
                {
                    op_efetuada == 'S';

                    printf("%s: \n",str);
                }
            }
        }

    }

  return 0;
}