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

typedef struct { int *t, nmax, n; }tas;

tas creer(int nmax)
{ return (tas) {malloc(sizeof((int)nmax)), nmax, 0};
}
tas detruire(tas a)
{ free(a.t);
  a.t=0;
  a.nmax=0;
  a.n=0;
  return a;
}
#define t(i) a.t[(i)-1]
void descendre(tas a, int i)
{ for(;;)
  { int k = 2*i;
    if(k>a.n) break;
    k+= k<a.n && t(k+1)>t(k);
    if(t(k)<=t(i)) break;
    int aux = t(i);
    t(i) = t(k);
    t(k) = aux;
    i = k;
  }
}
void monter(tas a, int i)
{ for(;;)
  { int k = i/2;
    if(!k) break;
    if(t(k)>=t(i)) break;
    int aux = t(i);
    t(i) = t(k);
    t(k) = aux;
    i = k;
  }
}
tas ajoute(tas a, int x)
{ a.n++;
  if(a.n>a.nmax) exit(1);
  t(a.n) = x;
  monter(a, a.n);
  return a;
}
void ordonne_tas(tas a)
{ int i;
  for(i=a.n/2; i; i--) descendre(a, i);
}
void ordonne_bis(tas a)
{ int n=a.n, i;
  a.n = 0;
  for(i=1; i<=n; i++) a = ajoute(a, t(i));
}
void ordonne_ter(tas a)
{ int i;
  for(i=1; i<=a.n; i++) monter(a, i);
}
void tri(int *tab, int n)
{
  tas a = {tab, n, n};
  ordonne_tas(a);
  while(a.n>1)
  { int tmp = t(a.n);
    t(a.n) = t(1);
    t(1)=tmp;
    a.n--;
    descendre(a, 1);
  }
}
tas pop(tas a, int *x)
{ *x = t(1);
  t(1) = t(a.n);
  a.n--;
  descendre(a, 1);
  return a;
}
void tri_bis(int *tab, int n)
{ tas a = {tab, n, n};
  ordonne_ter(a);
  while(a.n>1)
  { int x;
    a = pop(a, &x);
    tab[a.n] = x;
  }
}
void tri_ter(int *tab, int n)
{ tas a = creer(n);
  int i;
  for(i=0;i<n;i++) a=ajoute(a,tab[i]);
  for(i=n;i--;) a=pop(a,tab+i);
}
#undef t
void aff(int *t, int n)
{ while(n--) printf("%d ",*t++);
  printf("\n");
}

int main()
{ int n=100, i, t[n], j, x;
  void (*ttri[3])(int *, int) ={tri,tri_bis,tri_ter};
  for(j=0;j<3;j++)
  { for(x=i=0;i<n;i++) t[i]=x=(x*35+1)&2047;
    aff(t,n);
    ttri[j](t,n);
    aff(t,n);
  }
  return 0;
}