#include <stdio.h>
#include <limits.h>

/* as nossas listas terão elementos do tipo No */

typedef struct no_struct {
  int chave;
  struct no_struct *prox;
} No;

No *z; /* esta é a cauda de todas as listas */ 

/* inicialize_cauda: esta rotina deve ser chamada antes de começarmos
   a manipular as nossas listas.  Note que aqui pomos INT_MAX na chave de z
   para que ele possa fazer o papel de sentinela. */

void inicialize_cauda()
{
  z=(No *)malloc(sizeof(No));
  z->chave=INT_MAX;
  z->prox=z;
}

/* inicialize_lista: devolve um ponteiro para uma nova lista.  Devido
   a nossa convecao de que todas as listas terminam com z, isto é muito
   facil. */ 

No *inicialize_lista()
{
  return z;
}

/* insira: insere novo elemento no comeco da lista.  Note que devolvemos um
   ponteiro para o novo comeco da lista; não alteramos o ponteiro fornecido.
   */

No *insira(int v, No *comeco)
{
  No *x;
  x=(No *)malloc(sizeof(No));
  x->chave=v;
  x->prox=comeco;
  return x;
}

/* merge: executa o merge das listas cujos primeiros elementos são apontados por 
 * a e b.  Assumimos que estas listas estão em ordem crescentes nas chaves e 
 * produzimos uma lista nova com a uniao dos elementos destas listas.  As listas 
 * originais são destruídas.
 */

No *merge(No *a, No *b)
{
  No *c;
  c=z;
  /* z->prox será o começo da lista resultante durante o processo de merge.  A
     cauda (apontada por) z faz o papel de cabeça de lista para a lista sendo
     construída. */
  /* c apontará para o ultimo elemento da lista resultante até entao
     construída durante este processo  */  
  do
    if (a->chave<=b->chave) {
      c->prox=a;
      c=a;
      a=a->prox;
    }
    else {
      c->prox=b;
      c=b;
      b=b->prox;
    }
  while (c!=z);
  c=z->prox;
  z->prox=z;
  /* restauramos a condicao "z->prox=z" */
  return c;
}

/* mergesort: ordena a lista cujo início é apontado por c. */

No *mergesort(No *c)
{
  No *a, *b;
  if (c->prox!=z) { /* se temos pelo menos 2 elementos na lista */
    a=c;
    b=c->prox->prox->prox;
    while (b!=z) { 
      c=c->prox;
      b=b->prox->prox;
    }
    /* neste ponto, c aponta para o elemento que queremos que seja o último 
       elemento da primeira lista, i.e., apontada por a */
    b=c->prox;
    c->prox=z;
    /* produzimos duas listas, dadas por a e b, que têm basicamente metade de 
       elementos de c cada uma */
    return merge(mergesort(a), mergesort(b));
  }
  return c; /* se temos menos de 2 elementos na lista */
}

/* main: nada muito excitante aqui... */

main()
{
  int k;
  No *p;

  inicialize_cauda();
  p=inicialize_lista();

  while (scanf("%d", &k)>0) 
    p=insira(k,p);

  p=mergesort(p);

  while (p!=z) {
    printf("%d ", p->chave);
    p=p->prox;
  }
  printf("\n");
  return 0;
}