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

#include "globals.h"
#include "list.h"
#include "hrpa.h"

#define MAX_LIST_NUM 10
#define MAX_INPUT_SIZE 20

void merge(List *lists, int m, List *result) {
    Hrpa my_heap;
    Pair par;
    int i;

    hrpa_make_null(&my_heap);

    /* Postavljanje parova (prvi el. liste, indeks liste) za svaku
     * listu na hrpu */
    for (i = 0; i < m; ++i) {
	par.first = list_retrieve(list_first(&lists[i]), &lists[i]);
	par.second = i;
	printf("Ubacujem '%c' iz liste %d.\n", par.first, par.second + 1);
	hrpa_insert(par, &my_heap);
    }

    while (!hrpa_empty(&my_heap)) {
	/* Dodavanje najveceg elementa na kraj liste result */
	list_insert(hrpa_top(&my_heap).first, list_end(result), result);
	/* Brisanje vrha hrpe i dodanog elementa iz odgovarajuce liste */
	i = hrpa_top(&my_heap).second;
	printf("Izbacujem '%c' iz liste %d.\n", hrpa_top(&my_heap).first, i + 1);
	hrpa_delete_top(&my_heap);
	list_delete(list_first(&lists[i]), &lists[i]);
	/* Ako je i-ta lista jos neprazna, dodamo par (prvi el. liste, i)
	 * na hrpu */
	if (!list_empty(&lists[i])) {
	    par.first = list_retrieve(list_first(&lists[i]), &lists[i]);
	    par.second = i;
	    printf("Ubacujem '%c' iz liste %d.\n", par.first, par.second + 1);
	    hrpa_insert(par, &my_heap);
	}
    }
}

int main(void) {
    int i, j, m;
    char input[MAX_INPUT_SIZE + 1];
    List my_lists[MAX_LIST_NUM], result;
    position p;

    scanf("%d", &m);
    for (i = 0; i < m; ++i) {
	scanf("%s", input);
	list_make_null(&my_lists[i]);
	for (j = 0; j < strlen(input); ++j)
	    list_insert(input[j], list_end(&my_lists[i]), &my_lists[i]);
    }

    list_make_null(&result);
    merge(my_lists, m, &result);

    printf("\nSortirana lista: ");
    for (p = list_first(&result); p != list_end(&result); p = list_next(p, &result))
	printf("%c", list_retrieve(p, &result));
    printf("\n");

    return 0;
}