#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif
#define ID_GETLINE  1001
#define ID_DATANODE 1002

#define BUFFSIZE 1024 /* >= 2 */
char *mygetline(FILE *fp) {
  static char inbuff[BUFFSIZE];
  char *outbuff_malloc, *tmpbuff;
  char *p, *r;
  int fEOL;
 
  if ((outbuff_malloc = xmalloc(1, ID_GETLINE)) == NULL) {
    return NULL;
  }
  *outbuff_malloc = '\0';
  fEOL = 0;
  do {
    r = fgets(inbuff, BUFFSIZE, fp);
    if (r == NULL)
      break;
    for (p = inbuff; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n')
      fEOL = 1;
    if ((tmpbuff = xrealloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1, ID_GETLINE)) == NULL) {
      xfree(outbuff_malloc, ID_GETLINE);
      return NULL;
    }
    strcat(tmpbuff, inbuff);
    outbuff_malloc = tmpbuff;
  } while (!fEOL);
  if (strlen(outbuff_malloc) > 0) {
    for (p = outbuff_malloc; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n')
      *(p - 1) = '\0';
    return outbuff_malloc;
  }
  xfree(outbuff_malloc, ID_GETLINE);
  return NULL;
}

struct datanode {
  void *data;
  struct datanode *next;
};

void push(struct datanode **root, void *data) {
  struct datanode *p;
  if ((p = xmalloc(sizeof(struct datanode), ID_DATANODE)) != 0) {
    p->data = data;
    p->next = *root;
    *root = p;
  }
}

void *pop(struct datanode **root) {
  void *data;
  struct datanode *p;
  data = 0;
  if (*root != 0) {
    p = *root;
    *root = p->next;
    data = p->data;
    xfree(p, ID_DATANODE);
  }
  return data;
}

void sub_swap(struct datanode **p, struct datanode **q) {
  struct datanode *t, *s;
  if (&((*p)->next) == q) {
    assert((*p)->next == *q);
    t = *p;
    s = (*q)->next;
    *p = (*p)->next;
    (*q)->next = t;
    *q = s;
  } else {
    t = *p;
    *p = *q;
    *q = t;
    s = (*p)->next; /* in fact *p<=>*q but neet to do (*p)->next <=> (*q)->next */
    (*p)->next = (*q)->next;
    (*q)->next = s;
  }
}

void task_sort(struct datanode **root, int n, int (*comp)(void *, void *)) {
  struct datanode **p, **q;
  int i, h, flag, c;
  c = 0;
  h = n;
  do {
    h = (int)(h / 1.247330950103979);
    if (h == 10)
      h = 11;
    if (h < 1)
      h = 1;
    fprintf(stderr, "%d:%d\n", ++c, h);
    flag = 0;
    for (q = root, i = 0; i < h; q = &((*q)->next), i++)
      ;
    p = root;
    for (;;) {
      if (comp((*p)->data, (*q)->data) > 0) {
        flag = 1;
        sub_swap(p, q);
      }
      if (*p == 0 || *q == 0 || (*p)->next == 0 || (*q)->next == 0)
        break;
      p = &((*p)->next);
      q = &((*q)->next);
    }
  } while (flag);
}

int cmp_ascent(char *p, char *q) {
  return strcmp(p, q);
}

int cmp_descent(char *p, char *q) {
  return -strcmp(p, q);
}

int isSortOK(struct datanode *root, int (*cmp)(char *, char *)) {
  if (root->next) {
    if (cmp(root->next->data, root->data) >= 0) {
      return isSortOK(root->next, cmp);
    } else {
      return 0;
    }
  } else {
    return 1;
  }
} 
int main(int argc, char *argv[]) {
  struct datanode *root;
  char *p;
  int (*cmp)(char *, char *);
  int n, flag;

  if (argc != 2) {
label_usage:
    fprintf(stderr, "usage: %s <option>\n", argv[0]);
    fprintf(stderr, "option: -a: ascent, -d: descent, input/output: stdio\n");
    return 1;
  }
  if (*argv[1] == '-' && *(argv[1] + 1) == 'a')
    cmp = cmp_ascent;
  else if (*argv[1] == '-' && *(argv[1] + 1) == 'd')
    cmp = cmp_descent;
  else
    goto label_usage;
  
  n = 0;
  root = 0;
  while ((p = mygetline(stdin)) != 0) {
    push(&root, p);
    n++;
  }
  task_sort(&root, n, (int (*)(void *, void *))cmp);
  flag = isSortOK(root, cmp);
  while ((p = pop(&root)) != 0) {
    printf("%s\n", p);
    xfree(p, ID_GETLINE);
  }
  fflush(stdout);
  if (flag)
    fprintf(stderr, "Good.\n");
  else
    fprintf(stderr, "NG, there are some bugs in this program.\n");
  xmallocdump();
  return 0;
}
/* end */

usage: /t <option>
option: -a: ascent, -d: descent, input/output: stdio