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

typedef struct ENTRY {
	ENTRY          *before, *after;
	ENTRY          *same;
	unsigned char  *line;
	unsigned char  *sort_ptr;
	                ENTRY();
	               ~ENTRY();
};

ENTRY::ENTRY()
{
	before = after = same = 0;
	line = sort_ptr = 0;
}

ENTRY::~ENTRY()
{
	if (before)
		delete          before;
	if (after)
		delete          after;
	if (same)
		delete          same;
	if (line)
		delete          line;
}

int             column_flag = 0;
int             uniq_flag = 0;
int             num_flag = 0;
int             rev_flag = 0;
ENTRY          *eroot = 0;

void            read_one_data(unsigned char *s)
{
	ENTRY          *e, **eptr;

	e = new ENTRY;
	e->line = strdup(s);
	e->sort_ptr = e->line;
	for (int i = 0; i < column_flag; i++) {
		while ((*e->sort_ptr <= ' ') && *e->sort_ptr)
			e->sort_ptr++;
		while (*e->sort_ptr > ' ')
			e->sort_ptr++;
		while ((*e->sort_ptr <= ' ') && *e->sort_ptr)
			e->sort_ptr++;
	}

	eptr = &eroot;
	while (*eptr) {
		int             cmp;
		if (num_flag)
			cmp = atoi(e->sort_ptr) - atoi((*eptr)->sort_ptr);
		else
			cmp = strcmp(e->sort_ptr, (*eptr)->sort_ptr);
		if (cmp == 0) {
			while (*eptr)
				eptr = &((*eptr)->same);
			*eptr = e;
			return;
		} else if (cmp < 0) {
			eptr = &((*eptr)->before);
		} else {
			eptr = &((*eptr)->after);
		}
	}
	*eptr = e;
}

void            read_data(FILE * f)
{
	unsigned char   buf[1024];
	while (fgets(buf, 1024, f) != NULL) {
		buf[strlen(buf) - 1] = 0;
		read_one_data(buf);
	}
}

void            print_data(ENTRY * e)
{
	if (!e)
		return;
	if (rev_flag)
		print_data(e->after);
	else
		print_data(e->before);
	puts(e->line);
	if (!uniq_flag)
		print_data(e->same);
	if (rev_flag)
		print_data(e->before);
	else
		print_data(e->after);
}

main(int argc, char **argv)
{
	int             i;
	while (1) {
		if (argv[1][0] == '+') {
			column_flag = atoi(argv[1] + 1);
			argc--;
			argv++;
		} else if (argv[1][0] == '-') {
			switch (argv[1][1]) {
			case 'u':
				uniq_flag = 1;
				break;
			case 'n':
				num_flag = 1;
				break;
			case 'r':
				rev_flag = 1;
				break;
			}
			argc--;
			argv++;
		} else
			break;
	}
	if (argc > 1) {
		FILE           *f;
		f = fopen(argv[1], "r");
		if (!f) {
			printf("Can't open file %s\n", argv[1]);
			exit(1);
		}
		read_data(f);
		fclose(f);
	} else
		read_data(stdin);
	print_data(eroot);
}
