#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct data {
	size_t capacity, nmemb, size;
	void *base;
	int (*compar)(const void*, const void*);
};
struct data *init_data(struct data *data, size_t size, int (*compar)(const void*, const void*)) {
	data->capacity = 0;
	data->nmemb = 0;
	data->size = size;
	data->base = 0;
	data->compar = compar;
}
void ensure_capacity(struct data *data, size_t min_capacity) {
	void *newbase;
	if (min_capacity < data->capacity) return;
	
	newbase = realloc(data->base, data->size * min_capacity);
	if (newbase) {
		data->capacity = min_capacity;
		data->base = newbase;
	} else {
		exit(EXIT_FAILURE);
	}
}
int has_space(struct data *data) {
	return data->nmemb < data->capacity - 1;
}
char *chomp(char *cs) {
	if (!cs) return cs;
	int i = strlen(cs) - 1;
	for (;0 <= i && (cs[i] == '\r' || cs[i] == '\n'); i--) cs[i] = '\0';
	return cs;
}

// ----------------------
void print(struct data *data) {
	int i;
	for (i = 0; i < data->nmemb; i++) {
		printf("%d:%s\n", i, ((char **)data->base)[i]);
	}
	printf("capacity = %d, nmemb = %d\n", data->capacity, data->nmemb);
}
int normal_strcmp(const void *a, const void *b) {
	return strcmp(*(char **)a, *(char**)b);
}
int reverse_strcmp(const void *a, const void *b) {
	return strcmp(*(char **)b, *(char**)a);
}
void swap(char *a, char *b, unsigned width) {
	char tmp;
	if (a != b) {
		while (width--) {
			tmp = *a;
			*a++ = *b;
			*b++ = tmp;
		}
	}
}
void bubble_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
	int i, j;
	for (i = 0; i < nmemb; i++) {
		for (j = nmemb - 1; i < j; j--) {
			if (compar((char *)base + size * j, (char *)base + size * i) < 0) { // j < i
				swap((char *)base + size * j, (char *)base + size * i, size);
			}
		}
	}
}
void sort(struct data *data) {
	//qsort(data->base, data->nmemb, data->size, data->compar);
	bubble_sort(data->base, data->nmemb, data->size, data->compar);
}
int main(int argc, char **argv) {
	struct data data;
	char buff[256];
	init_data(&data, sizeof (char *), normal_strcmp);
	//init_data(&data, sizeof (char *), reverse_strcmp);
	ensure_capacity(&data, 512);

	FILE *f = 1 < argc ? fopen(argv[1], "r") : stdin;
	for (;fgets(buff, sizeof buff, f);) {
		if (!has_space(&data)) ensure_capacity(&data, data.capacity * 2);
	
		((char **)data.base)[data.nmemb++] = strdup(chomp(buff));
	}
	sort(&data);
	print(&data);
	return 0;
}