/*
 * Adaptado de K&R
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLINES 5000		/* Numero maximo de linhas que podemos manipular */
#define MAXLEN 1000

/* readlines(): le as linhas da entrada em lineptr */
int readlines(char *lineptr[], int nlines);

/* writelines(): imprime as linhas em lineptr */
void writelines(char *lineptr[], int nlines);

/* my_qsort(): funcao de ordenacao */
void my_qsort(char *lineptr[], int left, int right);

/**********************************************************/
int main()
{
  char *lineptr[MAXLINES]; 
  int nlines;			/* Numero de linhas na entrada */

  nlines = readlines(lineptr, MAXLINES);
  if (nlines >= 0) {
    my_qsort(lineptr, 0, nlines - 1);
    writelines(lineptr, nlines);
    return 0;
  } else {
    printf("Error: entrada muito grande.\n");
    return 1;
  }
}

/**********************************************************/

/* readlines(): le as linhas da entrada em lineptr */
int readlines(char *lineptr[], int maxlines)
{
  int len, nlines;
  char *p, line[MAXLEN];
  nlines = 0;
  for (;;) {
    p = fgets(line, sizeof(line), stdin);
    if (p == NULL)
      break;
    len = strlen(line) + 1;
    p = (char *) malloc(len);
    if ((nlines >= maxlines) || (p == NULL))
      return -1;
    else {
      strcpy(p, line);
      lineptr[nlines++] = p;
    }
  }
  return nlines;
}

/* writelines(): imprime as linhas em lineptr */
void writelines(char *lineptr[], int nlines)
{
  int i;
  for (i = 0; i < nlines; i++)
    printf("%s", lineptr[i]);
}

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

void my_qsort(char *v[], int left, int right)
{
  int i, last;
  if (left >= right)		/* Do nothing if array has fewer than */
    return;			/* two elements                       */
  swap(v, left, (left + right) / 2);	/* save the middle(pivot) position */
  last = left;
  for (i = left + 1; i <= right; i++) {
    if (strcmp(v[i], v[left]) < 0)	/* if the element is less than the pivot */
      swap(v, ++last, i);	/* move it to the left side              */
  }
  swap(v, left, last);		/* restore the pivot position */

  my_qsort(v, left, last - 1);
  my_qsort(v, last + 1, right);
}