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

#define TAMANHO_PALAVRA 51
#define TAMANHO_REGISTRO 52
#define MAX_FILENAME_SIZE 10

typedef struct tipoLivro{
    char registro[TAMANHO_PALAVRA];
    char disponivel; //Checa a disponibilidade
}Livro;

typedef struct tipoBuffer{
    Livro *item;
    int M;
}Buffer;

typedef struct tipoFita
{
    FILE *arquivo;
    int flag;
}Fita;

/*---------------------------------------------*/
/*                                             */
/*              Quicksort Interno              */
/*                                             */
/*---------------------------------------------*/

void Particao(int Esq, int Dir, int *i, int *j, Livro *A)
    {
        Livro x, w;
        *i = Esq; *j = Dir;
        x = A[(*i + *j) / 2]; /* obtem o pivo x */
        do
        {
            while (strcmp(x.registro,A[*i].registro)>0) (*i)++;
            while (strcmp(x.registro,A[*j].registro)<0) (*j)--;
            if (*i <= *j) {
            w = A[*i]; A[*i] = A[*j]; A[*j] = w;
            (*i)++; (*j)--;
        }
    } while (*i <= *j);
}

void Ordena(int Esq, int Dir, Livro *A)
{
    int i, j;
    Particao(Esq, Dir, &i, &j, A);
    if (Esq < j) Ordena(Esq, j, A);
    if (i < Dir) Ordena(i, Dir, A);
}

/*---------------------------------------------*/
/*                                             */
/*                                             */
/*                                             */
/*---------------------------------------------*/

void escreveRegistro(Livro *livro,FILE *output)
{
    fwrite(livro->registro,strlen(livro->registro),1,output);
    fputc (' ', output);
    fwrite(&livro->disponivel,1,1,output);
    livro->registro[0] = '\0';
    livro->disponivel = 'x';
}

void escreveBuffer(Livro *bufferLivros, FILE *output,int M)
{
    int i;
    for (i = 0; i < M; i++)
        if(bufferLivros[i].disponivel != 'x')
            escreveRegistro(&bufferLivros[i],output);

    fputs (" | ", output);
}


void esvaziaArquivos(Fita *fitas,int a,int b)
{
    int     i;
    char    fileName[sizeof"fita100.txt"];

    for (i = a; i < b; i++)
    {
        sprintf(fileName,"fita%03d.txt",i);
        freopen("fita%03d.txt,","w",fitas[i].arquivo);
        freopen("fita%03d.txt,","w+",fitas[i].arquivo);
    }
}

void intercala(Fita *fitas, int a,int b,Livro *bufferLivros,int M,int N)
{

    int     i; // Vai ser usado para controlar qual a ordem das fitas. EX: vao ser usadas as fitas 4,5 e 6. i=0 e a fita 4 e assim vai
    char    aux[TAMANHO_PALAVRA];
    char    menor[51] = {"{{{{{{{{{"};
    int     indiceMenor;
    int     k=0; // Conta qual arquivo destino está sendo usado
    int     j;
    int     escritas=0;
    int     totalEscritas=0;

    //Adiciona livros na memoria
    for (i = 0; i < M; i++)
    {
        if(bufferLivros[i].disponivel!='x' && fitas[i+a].flag==1 && fscanf(fitas[i+a].arquivo,"%s",aux) != EOF)
        {
            //Se não fim de bloco
            if(aux[0]!='|')
            {
                strcpy(bufferLivros[i].registro ,aux);

                if(strcmp(bufferLivros[i].registro,menor)<0)
                {
                    indiceMenor = i;
                    strcpy(menor ,bufferLivros[i].registro);
                }
                fscanf(fitas[i+a].arquivo,"%c",&bufferLivros[i].disponivel);
            }
        }
    }

    //Começa a intercalar
    while(1)
    {

        //Escreve o menor registro e o remove do buffer
        escreveRegistro(&bufferLivros[indiceMenor],fitas[b+k].arquivo);
        escritas++;
        totalEscritas++;

        if(escritas==N)
        {
            esvaziaArquivos(fitas,a,a+M);
            return;
        }

        //Pega o proximo registro na fita do menor que acabou de ser escrito
        if(fitas[a+indiceMenor].flag !=0 && fscanf(fitas[a+indiceMenor].arquivo,"%s",aux) != EOF)
        {
            if(aux[0]!='|')
            {
                strcpy(bufferLivros[i].registro ,aux);

                if(strcmp(bufferLivros[i].registro,menor)<0)
                    indiceMenor = i;

                fscanf(fitas[i+a].arquivo,"%c",&bufferLivros[i].disponivel);
            }
            else
                fitas[i+a].flag = 0;
        }

        //Verifica quantas fitas estão inativas e qual o menor indice
        j=0;
        sprintf(menor,"{{{{{");
        for (i = 0; i < M; i++)
        {
            if(bufferLivros[i].disponivel!='x')
            {
                if (strcmp(bufferLivros[i].registro,menor)<0)
                {
                    indiceMenor = i;
                    strcpy(menor ,bufferLivros[i].registro );
                }
            }
            if(fitas[i+a].flag==0)
                j++;
        }
        if(j==M)
        {
            k++;
            escritas=0;
            for (i = 0; i < M; i++)
                fitas[i+a].flag=1;
        }
    }
}

void voltaProInicioDosArquivos(Fita *fitas,int a,int b)
{
    int i;
    for (i = a; i < b; i++)
        fseek(fitas[i].arquivo,0,SEEK_SET);
}


// -----------------------------------------------------------------------//

int main(int argc, char* argv[])
{
    //--Variaveis--//

    int             N;      //Numero de livros na bibilioteca
    int             M;      //Numero de livros que podem estar na memória
    // int          E;      //Numero de estantes
    // int          L;      //numero de livros suportados por cada estante
    // int          K;      //numero de consultas a serem realizadas
    unsigned int    i,j,k;  //contadores
    char            fileName[sizeof"fita100.txt"]; //String que guarda o nome das fitas
    //char          aux[TAMANHO_PALAVRA];
    int             flag=0; //Usada para saber qual metade dos arquivos vai ser usada

    //Escaneando valores de entrada
    scanf("%d %d",&N,&M);

    //inicializando vetor de fitas
    Fita *fitas = malloc((2*M)*sizeof(Fita));

    //Abrindo arquivo de entrada
    FILE *input = fopen("input","r+");

    //Iniciliaziando vetor que simula a memória para guardar os livros
    Livro   *bufferLivros = malloc(M*sizeof(Livro));


    //---------Abrindo os arquivos das fitas---------//

    for (i = 0; i < (2*M); i++)
    {
        sprintf(fileName,"fita%03d.txt",i);
        fitas[i].arquivo = fopen(fileName,"w+");
        fitas[i].flag = 1;
    }

    //-----------------------------------------------//

    //---------Separando os primeiros blocos ordenados nas fitas---------//

    j=0;
    k=0;
    for (i = 0; i < N; i++)
    {
        fscanf(input,"%s %c",bufferLivros[j].registro,&bufferLivros[j].disponivel);
        j++;
        if(j==M || i==N-1)
        {
            Ordena(0,M-1,bufferLivros);
            escreveBuffer(bufferLivros,fitas[k].arquivo,M);
            j=0;
            k++;
        }
        if(k==M)
            k=0;
    }

    //--------------------------------------------------------------------//

    //---------Ordenando---------//




    //---------------------------//

    for (i = 0; i < (2*M); i++)
    {
        sprintf(fileName,"fita%03d.txt",i);
        fclose(fitas[i].arquivo);
        //if(remove(fileName)==-1)
        //  fprintf(stderr,"Aqruivo %s nao pode ser removido\n",fileName);
    }



    free(bufferLivros);
    free(fitas);
    fclose(input);

    //Ordena(0,M-1,bufferLivros);

    //fclose(entrada);
    return 0;
}