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

#define  MAXLINES   5000
#define MAXLEN     1000
#define ALLOCSIZE  10000

char *lineptr[MAXLINES];
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
int getline(char *, int);
char *alloc(int);
void qsort(char *lineptr[], int left, int right);
void swap(char *v[], int i, int j);
int strcmp(char *s, char *t);
void strcpyy(char *s, char *t);

int main()
{
  int nlines;

  if(( nlines = readlines(lineptr, MAXLINES)) >= 0)
   {
     qsort(lineptr, 0, nlines-1);
     writelines(lineptr, nlines);
     return 0;
   }
  else
  {
    printf("Error: input too big to sort\n");
    return 1;
  }
}


int readlines(char *lineptr[], int maxlines)
 {
   int len, nlines;
   char *p, line[MAXLEN];

   nlines = 0;

   while (( len = getline(line, MAXLEN)) > 0)
    if((nlines >= maxlines) || (p = alloc(len)) == NULL)
       return -1;
    else
      {
         line[len-1] = '\0';
         strcpyy(p, line);
         lineptr[nlines++] = p;
      }
     return nlines;
}

void writelines(char *lineptr[], int nlines)
 {
   int i;

   for(i=0; i < nlines; i++)
    printf("%s\n", lineptr[i]);
 }

void qsort(char *v[], int left, int right)
 {
   int i, last;

   if(left >= right) return;
   swap(v, left, (left + right)/2);
   last = left;
   for(i = left+1; i <= right; i++)
     if (strcmp(v[i], v[left]) < 0)
       swap(v, ++last, i);
   swap(v, left, last);
   qsort(v, left, last-1);
   qsort(v, last+1, right);
 }

void swap(char *v[], int i, int j)
 {
   char *temp;
   temp = v[i];
   v[i] = v[j];
   v[j] = temp;
 }

char *alloc(int n)
{
  if(allocbuf + ALLOCSIZE - allocp >= n)
   {
      allocp += n;
      return allocp -n;
   }
  else
   return 0;
}

int getline(char *s, int lim)
{
  int c, i;
  i=0;
  while(--lim > 0 && (c=getchar()) != EOF && c!='\n')
    { *s++=c; i++; }
  if(c=='\n')
   { *s++=c; i++; }
  s[i]='\0';
 return i;
}

int strcmp(char *s, char *t)
 {
   for( ; *s == *t; s++, t++)
    if(*s == '\0') return 0;
   return *s - *t;
 }

void strcpyy(char *s, char *t)
 {
   while(*s++ = *t++);
 }